When should pilots observe a "Sterile Cockpit"?
The "sterile cockpit rule" is an informal name for 14 CFR 121.542 and 14 CFR 135.100.  It says that no non-essential duties may be done during a critical phase of flight which is defined as "all ground operations involving taxi, takeoff and landing, and all other flight operations conducted below 10,000 feet, except cruise flight".  In your example, once they level off at cruise, even if it is below 10,000 feet, it no longer applies.

While this doesn't apply to Part 91 operations like you describe, it is a very good idea to follow the rule anyway to prevent distractions and increase the level of safety.

As far as the GPS, I would recommend fiddling with it on the ground before you takeoff and be familiar with its operation before you need to use it.  Being heads down for an extended period of time is never a good idea (unless you have a safety pilot along to keep an eye on things and look for traffic)!

The full text of the regulation is:


  §121.542   Flight crewmember duties.
  
  (a) No certificate holder shall require, nor may any flight crewmember
  perform, any duties during a critical phase of flight except those
  duties required for the safe operation of the aircraft. Duties such as
  company required calls made for such nonsafety related purposes as
  ordering galley supplies and confirming passenger connections,
  announcements made to passengers promoting the air carrier or pointing
  out sights of interest, and filling out company payroll and related
  records are not required for the safe operation of the aircraft.
  
  (b) No flight crewmember may engage in, nor may any pilot in command
  permit, any activity during a critical phase of flight which could
  distract any flight crewmember from the performance of his or her
  duties or which could interfere in any way with the proper conduct of
  those duties. Activities such as eating meals, engaging in
  nonessential conversations within the cockpit and nonessential
  communications between the cabin and cockpit crews, and reading
  publications not related to the proper conduct of the flight are not
  required for the safe operation of the aircraft.
  
  (c) For the purposes of this section, critical phases of flight
  includes all ground operations involving taxi, takeoff and landing,
  and all other flight operations conducted below 10,000 feet, except
  cruise flight.
  
  Note: Taxi is defined as “movement of an airplane under its own power
  on the surface of an airport.”




NASA has a great article called The Sterile Cockpit which goes into a lot more information, and includes some interesting statistics from the ASRS database about accidents/incidents that were in some way caused by not following this regulation:


  48% were altitude deviations
  
  14% were course deviations
  
  14% were runway transgressions
  
  14% were general distractions with no specific adverse consequences
  
  8% involved takeoffs or landings without clearance
  
  2% involved near mid-air collisions due to inattention and
  distractions.


Abiding by the sterile cockpit rule can help you to avoid situations like that! The article also gives some examples from the database and talks about a couple of crashes that were attributed to lack of compliance.