Provided both apps are from the same developer and signed by the same key, they should be able to share information privately. You could probably use a file (stored with MODE_PRIVATE)
, but I think the easiest route is to use SharedPreferences - set a flag in the paid app which will be read by the free one. See http://developer.android.com/guide/topics/data/data-storage.html.
No idea if it would be easy to circumvent, especially on rooted devices...
Another way would be to check if the paid app is installed, for example by checking if it accept a specific Intent. See also: http://developer.android.com/resources/articles/can-i-use-this-intent.html; in that example they check if ZXing's barcode scanner is available that way.
In any case, another twist on the idea would be that you could "enable" multiple apps with only one paying, if you so wished. Your paid app would be a simple "support this developer" which would remove ads from all your apps. That's an interesting paying model IMHO.