Secure keyboard application from android market
It's definitely a valid concern and you should be wary of apps that can record keystrokes with "Full Internet" privileges.

It's best to reach out to the developer of such keyboard app and ask them this question directly.  I imagine such a permission would be required for something benign, like downloading language packs (from within the keyboard app) or showing ads, for example.