3 differences
A good place to start is in understanding what users want and expect from mobile search, and mobile websites. The three key differences are browser technologies, screen size and search intent.

Mobile browsers have come a long way but they all latterly they share one thing, they need well formatted XHTML in order to work properly. There has been a shift in the way content is delivered too. Once WAP was the order of the day, but now there is more reliance on delivering http via call networks and Wi-Fi. These factors mean that it is easier to build mobile websites by importing practices from ‘regular' website design and development.

Even the biggest screened mobile device's/PDA's have limited screen real-estate- e.g. iphone's 480x320 on a 3.5 inch screen or Nokia's N810 with 800x480 on a 4.13 inch screen is never going to rival a desktop. Therefore the site that you build for mobile should be a different animal from your regular site.

When people search on a mobile device they're (usually) looking for a solution to a short-term problem; where is...?, how much is...?, what time is...?, can I book...?, can I download something specific to my device etc. etc.? Compare this with the broader searches that people use lap/desk tops for and you can quickly comprehend that mobile users want live data, and they want it now- they're less likely to be scoping out an e-book, or researching the best tumble dryer.

Mobile Search In Action
If you're new to mobile search or haven't bothered to see how it compares with regular search there are a couple of tools you can use from your desktop. This first one is from Opera, showing how its mini browser works. The other is an online example of how Google mobile works. Using the Opera tool enter the URL of a favourite site and notice the difference in how it's presented. Now, using the Google Mobile tool look at the difference in search results- these clearly show how sites and results behave in a different environment.

Search Optimisation for Mobile
Currently a common problem in optimising for mobile search is avoiding duplicate content, and the ranking penalties that it can incur. This mostly applies to Google, but there is some Google mobile advice to help you remedy any problems. The biggest issue seems to be in specifying which is your mobile content, and which isn't.

In part 2 of my mobile SEO blog I'll cover optimisation techniques in detail and offer advice on how to get the best from mobile search.