Say I walk into a store that accepts bitcoin. I decide to buy something and go to the counter. I get my smartphone out to pay the bitcoin. Does my smartphone need to have an internet connection to send the store my bitcoin?
Currently: yes, you pretty much need an Internet connection.
In the future: the relatively-new payment protocol BIP70 can be combined with Bluetooth, near-field communications (NFC), or possibly large QR codes to allow a merchant to send their address to your mobile device and your mobile device to send back a signed payment. Then the merchant will use their Internet connection to broadcast the payment.
There are a fair number of developers from organizations like BitPay currently working to make this as easy and seamless as possible, so you probably won't have to wait very long for beta-quality no-Internet-required in-store payment solutions.