The most important bit of advice anyone can get when optimizing a website for search engines and indeed for tools like Ultraseek is this...
Write your web pages for your human audience first and foremost. Don't do anything odd to try and optimize your website for a search engine. Don't stuff keywords into your URL if it makes the URL less sensible. Think human first.
Having said this, the following techniques usually make things better for both the humans and the machines!
Use headings (h1 through h6) to give your page a structure. Imagine them being arranged in a tree view, with a h1 containing some h2 tags and h2 tags containing h3 tags and so on. I usually use the h1 tag (there should be only one h1 tag) for the site name and the h2 tag for the page name, with h3 tags as sub-headings where appropriate.
Sitemaps are very useful as they contain a list of your pages, consider this a request of pages you would like included in any index. They don't normally contain much context though.
Friendly URL strings are great for humans. I'd much rather visit www.website.com/Category/Music/ than www.website.com?x=3489 - it does also mean that you give the machines some more context for your page. It especially helps if the URL matches your h1 and h2 tags. Like this:
www.website.com/Category/Music/
Website
Category: Music
Welcome to the music category!
Meta keywords (and description) are useful - but as per the above advice, you need to make sure that it all matches up. Use a small but targeted set of keywords that highlight what is specifically different about the page and make sure your description is a good summary of the page content. Imagine that it is used beneath the title in a list of search results (even though it might not be!)
Navigation! Providing clear navigation, as well as back links (such as bread-crumbs) will always help. If someone clicks on a search result, it might not be the exact page they are after, but it may well be very close. By highlighting where people have landed in your navigation and by providing a bread-crumb that tells them where they are, they will be able to traverse your pages easily even if the search hasn't taken them to the perfect location.