This is just a bunch of links of things I researched for connecting phones and arduinos and different ways of writing software for mobile phones. the image is a bluetooth rotary phone from sparkfun
iPhone
Develop native iPhone applications with Processing with iProcessing.
Sparkfun tutorial for controlling an Arduino with your iPhone. Uses the handy TouchOSC App. It’s not free, but it works fine with Max/MSP/Jitter and presumably anything that works with OSC which is most things.
And here’s an iPhone controlled LED suit!
Podgizmo’s iPod connector breakout board gives easier soldering access to the iPhone connector pins.
Android
Download the developer tools.
Android’s new Scripting Layer might make developing a tad easier. Supports Python, among others.
Processing for Android and a handy tutorial. The tutorial is very easy, but downloading all the software takes a bit.
Locale allows you to “create situations specifying conditions under which your phone’s settings should change.” Maybe an easy way to create locative media apps for Android. Costs $9.99 and has an developer platform.
Amarino lets you connect your Arduino to an Android phone. Requires Bluetooth 
Someone at Flake Labs looks like they’re trying another method that might be worth keeping an eye on.