Yes, you'll all need separate accounts for it to work properly.
You can all continue to use your shared iTunes account for app updates and song rights, etc. (even though you are not supposed to), but you will each need a separate iCloud account for messaging.
This is not really a bad scenario, though. Considering iCloud accounts are free to create from any iOS 5 device. The only downside is that if you want to upgrade your iCloud capacity or get iTunes Match, you will not all be able to get those features on the same account (again, unless you want to share an iMessage account).
Edit: On second thought there may be some kind of work-around involving the iMessage receiving settings on each device, but that might be tied to iCloud as well in backups, so I wouldn't count on it.