I would tell you ....
1- When you receive an SMS, add something to your queue
2- In your service :
Check your connectivity
- If your online : Get Queue list
For each action, do whatever you want to do and delete it from your queue list
- If you're not : Do nothing
3- Use CONNECTIVITY_CHANGE broadcast to check connectivity change and if you are connected. In this case,reproduces STEP 2. Else do nothing
Check http://developer.android.com/training/monitoring-device-state/connectivity-monitoring.html#MonitorChanges for monitoring change of connectivity (broadcast section)