I've been playing with this of late and it's very cool. This release focuses on local search, driving directions, traffic and maps. The release supports Windows Mobile and J2ME phones.
Installation is easy: point your mobile browser to http://wls.live.com/ and download the application.
Driving directions from Lake Forest Park to my Office (summary and map):
I may never get lost again!
LiveSide has a nice write-up at "Windows Live Search for Mobile Launched".