Tapbots' website just states 5.0 or newer is required so it should work. Here's their tips from their support page.
What is iCloud Sync? How do I get it to work?
With this feature, you can sync various things across multiple instances of Tweetbot (ex. between Tweetbot for iPad and Tweetbot for iPhone). Mute filters, DM read status, and your place in the timeline are all synced. So you can always continue reading where you left off between multiple devices. If you need to sync your timeline between other Twitter clients (like Twitterrific), you can change your sync service in the account settings to use Tweetmarker. Tweetmarker is a 3rd party sync service.
Getting iCloud Sync to work properly can be tricky for some. Here are a few steps to make sure you have everything set up correctly:
1) In the iOS settings, go to iCloud and make sure you are logged into the service (with the same iCloud account on both devices)
2) In the iOS settings, go to iCloud and make sure “Documents & Data” are enabled. If “Use Cellular” is turned off, iCloud Sync may not work if you are not on a wifi network.
3) In Tweetbot, go to your Settings -> Username (under Account Settings) -> Sync and make sure iCloud is selected on both devices for the same account
4) If it’s still not working, try rebooting your device. The next step would be to try re-installing Tweetbot on all your devices.
EDIT* One thing I've personally noticed is it only sync timelines if they are within a few minutes of each other. If you have gaps, it currently doesn't sync those.