the only times I have had these problems are obviously on iphone 3g/3gs but I imagine the causes are similar. possible causes are damage to antenna or the phone is blocked or barred. if this is your phone from new and your bills are paid then contact sim provider to make sure there is no reason for disconnection to network. take sim card out and clean/replace. reset network settings in settings. Have you opened the phone or dropped it? the iphone 4 is sensitive to greasy marks etc on the antenna flex.. as mentioned in all the repair guides.
if you have bought this phone 2nd hand I would check with the network provider that the phone isn't blocked or barred by them as a "stolen" or "lost" phone. You might like to do an online search too.. free sites don't tend to be updated as often as pay sites, but both will check imei isn't reported lost/stolen or subject to an insurance claim.
obviously if the phone isn't barred then you need to look at the antenna as a source of the problem