Does CLLocationManager work without internet/cellular connection?

Yeah it works if Location Services are enabled in the device settings. No need for Internet connection.

iPhoneiPadDev's answer is slightly wrong: whilst sometimes the location manager will fail, it can work without network connectivity. If you want to see this for yourself, go for a drive somewhere with terrible or nonexistent cellular reception: GPS will still work.

It very much depends on the environmental conditions around you, and the device you're using. iPod Touches and some iPads don't have GPS, and rely on WiFi hotspots to determine their location data. If you don't have network access the CLLocationManager will return an invalid location.

iPhones and 3G iPads do have GPS, so you may get an appropriate location returned. However, they use A-GPS (assisted GPS), which uses information from the network to allow a faster GPS lock. If you don't have internet connectivity it may take some time for the GPS chip to obtain a signal and provide an accurate location: and accuracy may be wildly off, if you're indoors or don't have plain sight of the sky.

Important point: CLLocationManager can and will return you locations even if none are available: the coordinates, however, will be invalid. It's important to test the locations being returned and make sure you're satisfied they are correct before using them.