Upgrading your skills is an essential part of Deus Ex gameplay. More importantly, selecting the right skills for your style of play is even more essential. You begin the game with Pistols upgraded to Trained and 5000 bonus skill points to spend as you wish.
For the stealth oriented, I'd recommend upgrading Pistol, Rifle (Sniper Rifle is unparalled IMHO) or Low-Tech (only for melee purposes), as well as upgrading Computer and later Electronics and/or Lockpicking.
For a brute force-oriented style, Heavy Weapons is a good first choice, and other compliments include Environmental Training, Lockpicking, Electronics and Demolitions. Medicine can be considered early, but later the regen augmentation will likely take over.
Simply click the picture of any skill below to bring up its description.