The solution I used, (and it's by no means the only solution), is to run the power through the arduino uno and connect the power from the 5v of the Uno to the Vin of the Yùn. The grounds are connected as well.
I found that a 9v battery, even though it powers the yun, does not provide enough current to power the wifi components of the board (or at least I could not get them to work with the battery).
With 4 AA batteries I got the wifi to work on the yun, however it took noticebly longer for wifi to load and respond.
The magic number was 6 AA batteries in a holder connected to the power jack of the uno. This provided load up and response times comparable with powering the Yun through the micro USB cable running to a wall socket or computer.