Hey Mark,
Aside from the queries that return hyperlocal results the only true differentiation for mobile search over Desktop is made for dump phones like Motorola RAZRs and early Blackberrys rather than iPhones and Androids. With that said the only difference for link building is that you should be submitting your site to mobile directories. Here is a short list of those directories to get you started.
Also there tends to be a big split amongst users over whether or not to use a full separate mobile site rather than just a mobile stylesheet. You should use the stylesheet in order to make use of link equity garnered by the desktop site.
Let me know if you have anymore questions!
-Mike