jroorda:
As for just plugging an Arduino into a phone, that won't work because they are both perifierals and neither is a host. Their are host shields for the Arduino, but things can get complicated going that route.
Modern Android phones support host mode with an additional cable. I just got a Micro USB OTG to USB 2.0 cable for my Samsung Galaxy S-II in the mail today. I was able to put a flash stick into the cable, and the phone had no problems reading it. I wouldn't try to power the Arduino with it (it may be the phone provides enough power, but I wouldn't count on it).