Absolutely free. Get yourself a Google Voice phone number. You'll have to link it to a phone you can make and receive phone calls on so you can complete the verification process. Once you do that, you can add your Tab's phone number as a linked number as well. When you do that, Google will call your Tab as well to ensure it's a real number. Obviously, you'll never get that call since the Tab has no phone function (at least not one you can easily access). Don't worry about that.
The next step is to install the Google Voice app on your Tab from the market. Open it up, go to settings, and select the option to "never make phone calls. " (though it doesn't really matter since the Tab can't anyway.)
That's it. Now go back to the app and open the menu. Select "compose" and text a loved one or yourself to make sure it works. The only caveat : texts will come from your Google Voice number, so if your contacts don't have it as one of your mobile numbers, they'll be wondering who is texting them the first time you do it. Once they update your information in their contacts list with your new number, they will know it's you. NEVER text from your Tab's number when you text from it. If people want to text your Tab, they should text your Voice number, NEVER your Tab's real number. And it goes without saying that the stock messaging app will no longer be of any use to you.

FREE texting. Oh, and Voice works over 3g and wifi. The paid messaging the rep was talking about is if you text to or from your Tab's real number.