I've noticed that most of the apps being released and updated recently have "iOS4 Tested" beside their product versions. How do I actually get my app "iOS4 Tested"? Do I have to rebuild/recompile my apps using SDK4 or simply make sure that it runs fine on an actual device running iOS4?
Ensure you build with SDK4 and test on iOS4 device. (Don't forget to test on OS3.x if you target is set to pre-iOS4, though.) If you are a registered developer, you should have received the answer to your question already from official sources...
It's just a check box that appears when you submit your app, if your app targets 3.x you will get the prompt to check that box, if you target 4.x you won't get the box because they assume you must have tested it on 4.x since it only runs on 4.x.
Hmmm I just submitted my app and I didn't see this checkbox anywhere on iTunes Connect. Can you please point me to the exact page/part?