How do I write an Arduino sketch and an Android application to talk to each other over a standard USB cable?
Android devices usually don't have a USB host: they expect to be connected to some smarter device like your computer. Same goes with Arduino.
For this reason Arduino made the Mega ADK (that means Accessory Development Kit).

Mega ADK and Due act as USB hosts and can be connected directly to your Android phone. If you already have a board, another option is to get a USB host shield to add USB host capababilities.

Your sketch will tell the phone what kind of accessory application it is and your phone will download the appropriate application from the store.

There is a book about connecting Arduino to Android.