Yes, it’s possible and should be automatic.
After you have created a CLBeaconRegion and started monitoring on it, Location Services will keep track of whether your phone is in or out of the region, even when your app isn’t running. If you app isn’t running during a transition, iOS will launch your app into the background for a few seconds to call the appropriate CLLocationManagerDelegate methods.
I found out the above behavior through experimentation with my own app, but have also witnessed it with Apple’s AirLocate sample program. With AirLocate, if you set up a monitoring region then reboot your phone, AirLocate will still deliver a local notification as soon as the phone enters the region.
Take care when testing this, because sometimes it takes up to 4 minutes after turning on/off an iBeacon before iOS recognizes the region state transition. EDIT: As of the iPhone 5, apps will typically use hardware acceleration to detect beacons within a few seconds, and if hardware acceleration is not available, it can take up to 15 minutes.
EDIT 3: AS of iOS 13, you must make sure the user actually grants background permission and not “only once” or “when in use” permission which are heavily pushed by the operating system in the dialogs they present to the user. See here for details.
EDIT 2: As of iOS 8, you need to make sure you have called and successfully obtained locationManager.requestAlwaysAuthorization() as locationManager.requestWhenInUseAuthorization() only lets beacons be detected in the foreground.
I have posted a detailed discussion on how this all works in this blog post.