You must find Pinkerton in Rivet City. He will let you change your appearance. Clarification: Pinkerton offers plastic surgery to change your actual face, but only after you've progressed to a certain point in the quest "The Replicated Man." If you just want to change your hairstyle (which will also change your appearance), there are several NPCs who will cut your hair for you. (In this case, "cut" can mean to make it much longer, which is kind of odd!) These include your robotic butler (Wadsworth in Megaton or Godfrey in Tenpenny Tower), one of the children in Little Lamplight, a ghoul in Underworld, and possibly others.
Additionally, if you are playing on a PC, you can activate the command console with the tilde (~) key and type showracemenu to bring up the gender / race / appearance selection screen. This is the same menu that appears optionally upon leaving Vault 101 for the first time if you elect to change your appearance at that time. You can use this function to change the appearance of your character entirely, and even get a sex change in the process if you want.
WARNING: on at least one occasion after using the showracemenu command, I noted that none of my PERKS were actually providing me with any bonuses afterwards. I still had the perks, but not the effects of them; for example, I lost the +1 to Strength from Ant Might and the damage resistance from Cyborg. This only happens on the PC version if you don't save and exit the game. You must do that to keep you current stats, perks, etc.
Changing your race resets all your perk bonuses to 0. You still have them listed but you get no bonuses. There is no fix for this. All other changes should be safe, it is only changing your race that causes this.