* First and foremost, make sure that your device has the latest firmware. In many cases, new firmware means support for Assisted GPS, a way of vastly speeding up GPS acquisition time - see my piece on this on AAS.
* Make 100% sure that 'Settings | General | Positioning | Positioning server' has the right access point - it should be set to your main 3G data provider, e.g. 'Vodafone live' or 'Orange Internet'. If this is wrong, then GPS locks will be several minutes at least on many S60 phones.
* Make sure you're in an area of data coverage - being stuck in the wilds or in a valley will mean no data, which in turn means no Assisted GPS.
* Don't try and get a GPS lock while moving, unless there's absolutely no alternative. It's hard enough as it is for your phone to lock onto half a dozen satellites whizzing overhead at thousands of miles per hour - adding in extra complications by moving the device itself just slows down lock times considerably.
* Be realistic if you are moving or if there are tall buildings around, or if you're in a vehicle with an incomplete view of the sky - locks may take several minutes. The reason why dedicated sat-navs can acquire GPS locks more quickly in these challenging circumstances is that they have higher power, more sensitive receivers on board - the GPS inside most smartphones tends to be of lower power, to save battery life.
* Don't cover up the GPS antenna. On the N95, this is at the bottom of the keypad, so extend the slide. Find out where the GPS antenna is on your device and don't cover it with your hand during use - human flesh is reasonably good at blocking radio waves.