This may be a bit early but I was asked to write something of this nature for a client and thought it worth sharing with you all.  I think the most significant trend of 2009 is the rise of Twitter, demonstrated by how I compiled this post - I didn't do endless Google searches, I asked leading SEO industry people on Twitter what they thought should be included.  Many thanks to them, you should all follow them as they are ace:

• @neyne
• @BenjaminHook
  
• @IngoGuava
  
• @peteyoung
  
• @jonaths
  
• @phillmidwinter
  
• @guavarian
  
• @dorksterdave

SEO Highlights for 2009

Vince:
Vince was an update in Google results that affected results around March 2009.  It is an update that was said to favour big brands in search results.  Research into how Vince favours brands in the search results indicates that brand search volume and search refinement may play a big part, which can be encouraged via other marketing channels and PR
More info: A Comprehensive Guide to Google Vince by @jonaths

Caffeine:
Caffeine is an update to the technology behind Google.  It should provide a faster experience and enable Google to update the search results with new features more smoothly.  In theory, as it only affects the underlying technology, search results shouldn't be affected, however Google is rolling this update out after Christmas to make sure any anomalies won't hurt the Christmas period.
More info: Google Blogpost on Caffeine

Bing UK:
Bing is the relaunched Microsoft search engine, formally called Live.  Bing is being marketed heavily in the US with a $100 million advertising campaign, pitching itself as a "Decision Engine".  It has partnered with several vertical search engines such as Wolfram Alpha and Ciao to provide richer results than Google, the biggest partnerships include taking over Yahoo search technology and close Twitter integration.
More info: Bing UK Features

Google Webmaster Tool Updates:
Several improvements were made to Google Webmaster Tools to help with SEO without needing to change code on the website - along with HTML (cough SEO) suggestions, tools such as site migration notification and parameter handling were introduced to help a webmaster diagnose what they can do to improve the indexing of the site.
More info: Google Webmaster Tool Blog

Canonical Tag:
Along with the Google Webmaster Tool updates, Google also coordinated with other search engines to introduce a new meta tag.  This can be inserted into a page to tell search engines which page should be regarded as the default and so avoiding duplicate content issues.  The Canonical tag acts as a suggested 301 redirect, the traditional method of canonicalizing multiple URLs (such as example.com, www.example.com and www.example.com/index.php
More Info: Google Introduce Canonical Tag

Linking more important in SEO industry:
In 2009 more SEO's recognised the importance of linking to achieve results, with more sophisticated linking techniques being used.  The reliance on link networks and paid links has in general trended downwards to more favour content creation.  This can be observed in the increasing sophistication of competitor backlinks.

Google Search Wiki:

Google introduced more personalisation into Google search results, with options such as Search Wiki letting users literally blow up results they don't want for keyphrases when signed into their Google account.  In general Google has been active in collecting more user data to help improve their search results, as can be seen in Google experiments such as social search. 

More info: Google's Search Wiki Introduction 

Google Sidewiki:

Sidewiki is a new addition that enables users with the Google Toolbar to comment on a website for other Google users to review.  The commented on website can only control which results appear if they sign up to Google services themselves. 
More info: Sidewiki abuse starts on UK papers by @malcomcoles, 

Lead Generation:
Google are increasingly looking to provide comparison services on the search results - mortgage comparison was sighted being trailed in the UK and Google Product search was recently updated to feature comparisons between products.
More info: Google tests Mortgage Comparison Ads

Google Book Search:
Google has been through some political wrangling to allow it to publish books online worldwide - this has recently been restricted to only those areas were publishers have rights, at the moment only those in the US, Canada and the UK.
More Info: Google Books legal settlement sets geographic, business limits

Wolfram Alpha / Semantic:
Wolfram Alpha was launched to much hype early in the year, and whilst traffic levels are not significant, Bing signed up an exclusive deal with Wolfram technology to provide Wolfram Alpha's content rich, supercomputer computed results into search results.  Wolfram is an example of a semantic search engine, where output it guessed via the context of the query.  The data is all curated in Wolfram's own servers though, so is not a true semantic search engine that would recognise general user data as this would require non-standardised recognition of context.  Google is also in this area with Google Squared

More Info: Tim Berner's Lee TED talk on "The Next Web"

Social Media growth (Facebook/Twitter)
Social Media in general continued to grow, with Twitter becoming mainstream through highly publicised events, such as the Trafiga scandal.  Facebook continued its staggering rate of growth, with now 1 in 7 pageviews in the UK belonging to Facebook.com.

Google Chrome
Google launched its own browser in competition with Firefox and Internet Explorer.  The browser boasted Google's clean design and a new Javascript engine which at the time was at least 3 times as fast as its nearest rival. 
More Info: Google Chrome Features

UK Serps:
At the same time as the Google Vince update, UK SEO's started to notice non-local results appearing in Google results.  In some cases, searching for products only showed irrelevant foreign results, useless to the user (For example "tennis courts in exeter" bought back no UK results)  This was posed as an unexpected by-product of the Vince update, and no clear answer or solution has been forthcoming from Google on when this problem is recognised or attempted to be fixed.
More Info: Matt Cutts responding to our very own @Guavarian about UK SERPs

Nofollow Pagerank sculpting:
Matt Cutts at an SEO conference shocked many SEO's by announcing that the practice of "PageRank Sculpting", specifically the technique of using "nofollow" to flow PageRank to a website's most important pages, will be of no benefit and may in fact be detrimental.  Matt Cutts further rubbed salt in the wound by announcing "nofollow" PageRank sculpting had been like that for at least a year, but no one in the SEO industry had noticed.
More Info: Matt Cutts clarifies about PageRank Sculpting

Paid Links - Google Japan:
On the other foot, an embarrassing incident in Google's battle against webmaster's using paid links to manipulate rankings was created by Google Japan admitting using pay-per-post schemes to help inflate its own website Yahoo Japan rankings, where Yahoo is the dominate player.  Google responded by lowering the toolbar PageRank of the site to PR5, a move which was largely symbolic.
More Info: Google Japan Penalized for Paid Links

Javascript/Flash Indexing:
With increased reliance on non-HTML content on the web, such as Javascript AJAX and Flash, Google has been working to index more content of this nature to help with search relevancy.  Whilst a Flash URL link is not thought to be of the same power as a standard HTML link, Google has been rolling out over the year improved handling of Flash and Javascript content.
More Info: Advances in Javascript/Flash indexing, but is it enough?

Meta Keywords Tag:
Google officially confirmed that the meta keyword tag has no affect on search position.  Whilst known for many years in the SEO community that meta keywords had little or no effect, this confirmation put the final nail in the coffin for this early web meta tag, a victim of being too easy to spam to be of any use to search results.
More Info: Google does not use meta keywords tag

searchga.me
All the fun of the SEO fair at @sharkseo's SEO game.  Give it a go!

I've probably missed some, if so let me know via @GuavaUK or comment below and I'll add them in.

Looking ahead to 2010

So that was 2009, what can we expect to see in 2010?

Page Load times:
Google have recently announced that page load times will increasingly become a ranking signal in search results, with the aim of encouraging the general improvement of the WWW experience for the browser.  This has been suspected to be the case for a few years, confirmed by Google.

Social Search:
Bing and Yahoo have recently announced integration with Twitter into their search results, in the first instance allowing relevant tweets in your network be displayed in your keyword searches, but moving forward we could see more search personalisation based on your activity on social media sites.

NewsGroup dropping Google:
2010 will be an interesting year to see how Google's relationship with online newspapers develops - NewsGroup are looking to go behind a paywall as soon as possible to try and halt the decline of online revenues, accusing Google of using NewsGroup's own content for its own gain.  Many publishers will be watching to see how successful the operation is.

Location based social media:
The rise of smart-phones with GPS and location aware browsers means more data can be used to help functionality of web applications, including local search results.  Ideally in the future typing in "pizza" will give you the closest pizza shop to your location.  Location based social media sites such as FourSquare may also gain popularity.

HTML 5:
HTML 5 was further specced out in 2009, with features such as semantic tagging implemented.  This will be firmed up more in 2010, although HTML5's effect on SEO won't be noticed for a good few years until the majority of websites start using it as standard.  Microformats and RDF will be coming a lot sooner.