App Updates - Are they dependent on Google Market? I noticed on another android phone there were "updates" such as new Youtube, Gmail, etc. I never received a notification for these on my device. Are these delivered via Google Market, or is there another app I can use to update these other than Google Market?
App updates notification can come from the app themselves, but most commonly they come from the Play Store. Play Store will notify you for any updates to system apps (i.e. apps that originally comes with the phone) and apps that are installed through the Play Store; it won't notify you about updates to side-loaded apps our apps installed by third party market.

Third party market may also have their own update notification mechanism; which is completely unrelated to the Play Store update mechanism. They may or may not provide update to system apps, although most don't. Amazon App Market for example also provide updates notification. Note that update notification on third party market depends on the app developer updating the app on the third party market, some developers might update their app on Play but not on third party market or vice versa for various reasons.