Off the top of my head, but whenever we do SEO at work it really differs on a per-site basis. Be graceful in what you do, don't end up keyword stuffing or generally making the website look retarded & spammy.
Uh... okay so this became quite a long list... and it's late. Remember SEO is all theory, Google don't tell you exactly what they do to rank pages.
- Sign up with google and do their webmaster tool validation stuff, although it proably won't do much, you should do it anyway
- Begin page titles with most important keywords. Think what people will google for, e.g. "Roof Tiler in Worthing - Charles and Son Ltd" is a better title for SEO than "Charles and Son Ltd" if you are a roof tiler in worthing.
- Keep the title <65 characters long
- Have a different title for each page
- Make the title interesting if possible (if someone sees it in Google, why should they click yours, not the next listing down?)
- The above two points again, but for meta description
- No more than 10 meta keywords if possible, you want to keep them specific
- Target a certain phrase throughout all your page content, e.g. Roof Tiler in Worthing/Roof Tiler/Roof Tiling without keyword stuffing. Just be clever about it, not obvious.
- Target each page (titles,meta data,body text) differently - e.g., the home page for "Roof Tiler in Worthing", the contact page for "Free Roof Tiling Quotation Worthing", and so on.
- Change page content reasonably often to keep Googlebot coming back
- Submit a site map to Google
- Have a HTML site map available
- Validate your site to ensure good HTML markup and spider-ability
- Avoid unnecesarrily hiding text with CSS, Google (probably) ignores hidden text unless you do some dodgy text-indent to hide it. But why hide good copy text anyway?
- Use bold tags on important keywords
- Make sure each page has a different H1, and that it isn't exactly the same as the page title (take a pinch of salt there, it may be OK to have it the same as the title, but I always avoid it)
- Put your targetted keyphrase/keyword in the H1
- Make use of H2's and H3's too
- Your Domain name shouldn't be closer than 12 months until renewal (spam sites and unstable sites tend to disappear, decent sites stay around longer and have further expiry dates)
- Submit to directories like DMOZ and Yahoo
- Build links to your website from directories and other relevant sites wherever possible, but don't spam
- Get a blog on your site and post something 2+ times a week
- Submit that blog to Technorati
- Make good use of 404 pages, but broken links should always be fixed, or at least 301'd to keep link juice flowing
- Image tags shuold have useful alt text
- Put title tags on links (<a href="x" title="Roof Tile Quotation">)
- Use meaningful text in links, never say "click here" to link to a quotation page, say "Get a Roof Tiling Quote" instead.
- Link to other (relevant) websites
- Don't become part of a "bad neighbourhood" (don't link to spammy sites or submit your site to dodgy directories)
- Use human-friendly URLS with keywords in (try mod_rewrite on apache for dynamic pages)
- Read SEO blogs very often and keep up with geniune sounding techniques and ideas, but keep a bowl of salt near by

- Keep a good amount of copy (plain text) on each page, not too many images or too much flash
- Don't use too many subdirectories in your site, aim for no more than 3 slashes in the URL
- Spell everything properly
- Don't have unneccessarry HTML code in the page, include CSS and JS externally.
Like I say, there will undoubtedly be much more to be done on your site, but this lists a lot of the generic "must-have" SEO tips. I don't think I've said anything stupid or twice (or stupid and twice), but it's late, so forgive me if I did
