Short answer
If you want to avoid a computer connected directly to an Arduino over USB or Ethernet, I recommend using a wireless option like 802.11, Bluetooth, ZigBee, or RF. I'll warn you right now, an Arduino cannot process video. It doesn't even have enough memory to store a higher resolution video frame. I recommend starting without the camera and just sending basic navigation commands using the wireless option.
Long Answer
Arduino has a concept of shields. These are modules you can add on to the Arduino for extra functionality. To get the Arduino to communicate over a wireless connection, options include the WiFly shield for 802.11B, XBee shields and adapters to connect over the ZigBee protocol (a low bandwidth, energy efficient protocol), Bluetooth Arduinos for Bluetooth connections and even straight up RF options (see JeeNode).
Most shields are not directly compatible with the Arduino Nano however. That doesn't mean you can't use them, just that you may have extra work related to wiring up the pins.
From a programming perspective, the easiest way to communicate is over the Tx/Rx lines of the Arduino. This is a basic serial connection that's easier to understand. See the Serial page for more details.
The audio output of your smartphone is fitted with a bandpass filter: high pass to protect the membrane of your earbuds/speakers against DC which would cause useless mechanical stress, and low pass to make sure as little noise is heard. Since audio is roughly 20Hz-20kHz, signals with a higher frequency will get attenuated at a rate depending on the order of the filter - at least -3dB/decade.
In fact, that output can't even accurately output digital signals up to 20kHz. Why? Because the sharp edges of the digital signals are made up by an infinite number of elementary sinusoids. The lower the cutoff frequency, the more harmonics you'll attenuate, distorting the signal like this:
You may filter what you measure to try and reconstruct the square wave but still, it's not very appealing.
Now, you can increase the datarate for a reasonable carrier frequency (say, 4kHz), by changing the modulation and/or encoding. Modulation is the process that transforms the data to send into a signal to apply to the transmission medium (through power amp. + antenna for example) - the transport layer if you will. Encoding is higher level, it deals with anomalies detection and correction. Yours is by default certainly in its simplest form (parity bits, compared to more advanced state machines etc.), but the first step to take to increase the datarate for non-critical communication is modulation.
There is a range of possible modulation techniques out there. Each one of them will have a different signal to noise ratio - error rate relationship and also a different symbol rate out for a given datarate in.
Among all of those, I recommend the simplest digital amplitude modulation. As you increase the number of possible output levels, the signal to noise ratio will decrease so you'll have to find the sweet spot. To increase your datarate by N, you'll need to be able to read 2^N different levels.
Note: Forget about the carrier (the medium is not air, so no need for RF), and in this example 0 is coded with some amplitude but it doesn't need to be.
Should you need more, you could improve your encoding to decrease the required signal to noise ratio and therefore increase the number of levels a bit further. If it's not enough, take a look at a more complex technique, e.g. QAM. ADSL used that modulation to boost the datarate on the same lines; I don't remember the symbol rate, but the carrier was around 1MHz to avoid interfering with the telephone < 4kHz, and they achieved at least 512kb/s at the time, impossible to achieve without a very dense modulation. I'm not sure if the Arduino is powerful enough for this plus your application though.
Best Answer
A major problem with low-frequency sound is the size of the transducer you need to transmit it efficiently, and the bandwidth you can achieve, which will restrict the data rate. Low-cost wireless transceiver modules using the Nordic nRF24L01+ device are available ($4), with Arduino code, and will work much better.