Yes it's possible. But for that you need the phone to install unverified sources. For example, slideMe does that. I think the best thing you can do is to check if the application is present and send an intent for the Android Market. you should use something the url scheme for android Market.
market://details?id=package.name
I don't know exactly how to start the activity but if you start an activity with that kind of url. It should open the android market and give you the choice to install the apps.