Forum Moderators: open
As per the question, I'd think that if a search engine came along that was really cool and worked significantly better than Google/Yahoo, then it wouldn't need any marketing - word of mouth (online and offline) would be enough.
However if its a niche search engine (e.g. useful for people with disabilities) then you could ask for links on related sites or post on related forums.
If you know of anyone who'd find it useful (friends/family) then tell them about it and go through it with them. This will kickstart some traditional word of mouth activity, while highlighting any improvements you may need to do.
[edited by: TravelSite at 1:24 pm (utc) on Mar. 26, 2007]