508 Standards, Section 1194.22 (a) states that:
A text equivalent for every non-text element shall be provided (e.g., via "alt", "longdesc", or in element content).
For a searchbox, using
<input type="text" alt="Search" value="" tabindex="1" name="s" id="s" />
passes the 508 Standards, but doesn't pass HTML 5 validation.
Is using <label> tags the only way of passing both the 508 Standards and the HTML 5 validation, because I would like to avoid having an unnecessary <label> tag?
I think you need to page more attention to 1194.22 (n) in this situation. If you really, desperately need to do without a separate label you could try something like this:
<input type="search" value="" tabindex="1" name="s" id="s" />
<label for="s"><input type="submit" value="search"></label>
But I would strongly recommend at least trying this out in a screenreader (NVDA is free, JAWS can be used for 40 minutes on a 'free trial') or, even better, setting up a test page and getting some screen reader users to try it.
Alternatively you could investigate aria-labelledby and see if that allows you to fit in your label more naturally.