The Legend appeared all of a sudden in version 2.2.3 for me too. I have no idea why this is.
But the easiest way to change this is to copy the SearchForm.ss from /sapphire/templates to your own templates dir and edit it ....
Silverstripe will then automatically use this template-snippet to create the simplesearch form.
The legend is a required tag for HTML strict validation (or WCAG) if I am not mistaken. I think I added that to the core template as part of a project to make it compatible. You can just hide it like Cyl has mentioned in the CSS file