I'm mostly interested in a general answer for mobile, but something android specific would be acceptable.
Given 2 mobile devices, how can I get a connection between them. I'm new to mobile development, and I'm not sure what kind of NAT mobile devices are behind. Is it possible to do some sort of "hole punching"(using an outside server to aid in getting a connection) to connect them together?
I've looked at this question, but it didn't help me too much, I still don't know how to get an IP and/or traverse a NAT. Android - communicating between two devices
If you want to use general wireless module, like GSM, UMTS, LTE you need to provide standalone hardware with implementation of desired protocols. For GSM you could look into OpenBTS http://openbts.org/ which is free software.
As other communication possibilities, you can use Wi-Fi Peer-to-Peer http://developer.android.com/guide/topics/connectivity/wifip2p.html for establishing wifi connectivity.
Communication abilities are based on a chip's specifications, not all wi-fi support this kind of connection. On the other hand you can also establish Bluetooth connectivity.