It's not an automatic push from your Mac to the cloud. Apple got into some hot water about this because they claimed everything was push when MobileMe was released. I believe it's more like fifteen minutes, but it depends on when the last sync was.
Sometimes when you add a new contact ..You might want to go to the MM settings on your Mac and click syncnow.. There are a few options.. Automactically,everyday,everyhour,and manually.. Not what best fits your needs.. But you can always hit the syncnow button. Just make sure your phone is set accordingly