Yes, it needs something on the device, but it doesn't need to be running.

Even iOS4 apps could be woken by the OS when geofences were crossed. Pick the right level of granularity and it didn't even need to use GPS - it just got woken by the baseband when the local cells list (which is updated every ~2.5 seconds when the baseband wakes up to check for pages)... ie, basically zero extra power over standby.

Not that I've seen any geofencing app that works properly apart from reminders on iOS5, though... and that uses GPS