It's stored on the servers of the marketplace (Google Play or Appstore). I don't know if the device needs to be online.
You can store the purchases in the app, but you still need to check if the product is owned when the app is launched for the first time - in case the product has been purchased before on a different device, or the app was re-installed.
Also, people can refund the purchase. So it's still recommended to check if the product is owned occasionally.