Good UX is an uninterrupted, smooth engagement with the tool (software or not).
If I understand your explanation correctly, a notification is something that informs the users of a new version or a product by the same producer in a rather intrusive way (be it a modal pop-up or a message in the notification area). Such a method of selling is generally intrusive and doesn't constitute a good experience because it breaks users' attention & flow.
What follows below might send lots of hate rays my way from my UX brethren.
If you are OK with such interruptions (though, again, they're extremely not recommended), the least damaging placement is showing a modal pop-up at application's launch with two buttons: Learn more and Dismiss and the option of Never show these again.
Alternatively, you can place ads/notices as a form of a "loading" screen for your application. In this case, the screen would need to be visible for no more than 2-3 seconds or your app might feel too slow. The visibility time also means you would need to put a very short copy & a clear call to action ("Learn more" or "Download now") or users won't be able to comprehend the message.
Finally, you can include a link to "See our other apps" in your changelog screen. The business downside is that such a screen makes sense to be shown only upon application updates. If you don't update often, your users won't see it often.
Now, let's talk about UX-friendly ways of converting free users into paying customers.
The ideal method is to provide a fully-featured app that is constrained by usage. The easiest example is ReadItLater app that limits access to just 10 most recently saved articles. (It also has some features disabled but they're minor ones.) With such an approach, your users are able to evaluate your app fully and see whether it fits their needs/wants. However, you need to watch out for having relaxed usage limits (i.e. providing just enough free access to fit the needs of the majority of users) as that will hurt your conversions.
The less ideal method is to provide a limited-functionality trial. This seems to be the most common method in app stores of all platforms. Users are converted by linking the disabled features to the full version's app store page or through nagging reminders. The downside is that you might restrict access to the key functions, which will be the deciding point to some customers, and which will create a negative impression about your product.
In the end, it's your call. The non-UX-friendly methods are likely to bring more revenue because like the misleading Dark Patterns they're highly intrusive and visible. However, if you want to be known as a reliable, quality developer you'll need to bite the bullet and convert users by providing a smooth experience and highly value product.
Added on Feb 1
Here's an example of a modal window promoting other apps by ClockworkMod shown at the first launch after an update. You can see that it's slightly misleading because it's hard to discern where the list of features ends and where the promotion begins. Also, the buttons linking to the promoted apps feel like controls for the app rather than external links. Thus, make sure that your message is clear when using this pattern.
