Either build a serial cable for your Android phone, like this one for the G1, http://www.instructables.com/id/Android-G1-Serial-To-Arduino/.
Or add a Bluetooth module to your Arduino,
or use an Ethernet-shield for your Arduino and connect via TCP/IP.
Which one to use depends on your project and your budget. I don't know if the serial cable option exists for phones other than the G1. The Bluetooth module has the advantage of beeing wireless for both, the Arduino and the phone, and using the Ethernet-shield you could make the Arduino worldwide accessible by using port-forwarding on your firewall.
I've been working with Amarino since they started and I haven't had a problem since. However I have no experience with other projects since I have only worked with one.
These are my two favorite opensource devices though. Way to go with not joining the iPhone band wagon. It really pleases me when there is someone who takes the initiative to go far and beyond, because it shows that your thinking about the long run. Most people don't.