Basic test of iCloud: Go to iCloud.com. What you find will help you determine whether contacts on your iPhone (or Mac) are being successfully pushed to iCloud, and whether the contacts in iCloud are being successfully pushed out.
A couple of more tests:
Make sure your Mac is fully logged into iCloud. Go to System Preferences > iCloud > Account Details. If it asks for your password before revealing Account Details, you weren't fully signed in.
Make sure the contacts on the iPhone are actually in an iCloud Group (iPhone > Contacts > Groups), and make sure all those same groups are present in Contacts on the Mac.
If you expect new contacts to make it into iCloud, rather than, say, Gmail or On This iPhone, make sure that you've selected an iCloud group as the default for new contacts (iPhone: Settings > Contacts >Default Group Mac: Contacts > Preferences > General > Default Account)