May pilots perform FMS database updates under Part 135?
Updating a navigation database used to be considered preventative maintenance and was required to be performed by a mechanic under Part 135.  However, the regulations were changed at the end of 2012 (here is the final rule) and it no longer falls under this category so pilots are allowed to update "aeronautical databases" (a new term) if it is "easy" to do (see the regulation quoted below for the exact requirements).  There is no training requirement specified by the regulations, however there may be company specific procedures which require it.  

14 CFR 43.3 was updated, and now says (in part):


  (k) Updates of databases in installed avionics meeting the conditions
  of this paragraph are not considered maintenance and may be performed
  by pilots provided:
  
  (1) The database upload is:
  
  (i) Initiated from the flight deck;
  
  (ii) Performed without disassembling the avionics unit; and
  
  (iii) Performed without the use of tools and/or special equipment.
  
  (2) The pilot must comply with the certificate holder's procedures or
  the manufacturer's instructions.
  
  (3) The holder of operating certificates must make available written
  procedures consistent with manufacturer's instructions to the pilot
  that describe how to:
  
  (i) Perform the database update; and
  
  (ii) Determine the status of the data upload.