Looking at the default TTL of Android, it appears to be 64. My laptop (Ubuntu) is also 64. So I changed /proc/sys/net/ipv4/ip_default_ttl to 65 on the laptop, raising the TTL by one. So if my carrier is paying attention to this, packets should appear to originate from my smartphone, rather than 1 hop behind it.
Next, if I connect to a VPN from my laptop... that should prevent them from seeing that I am connecting to Windows Update (or other obvious non-smartphone services) or from reading the user-agent, as the VPN encrypts the packets.
This, I think should be sufficient, right? I do not intend to use an insane amount of data anyways. The carrier is Sprint, and they've never mentioned anything to me before. Do you think they would investigate any further than this for signs of hotspot use? I hope that this is an appropriate category to post this, I tried under Galaxy Nexus Q&A but did not get any answers.