Every time you kill an enemy with an explosion, your explosives rating goes up. When you kill a civilian or police officer in the same way, it goes down. Explosions can be gained with rocket/grenade launchers, grenades/mines, or shooting explosive barrels or cars. The single best tool for this is the Firefly rocket launcher, which homes in on the target. The Firefly rocket launcher can be found in the Shai-Gen territory in the possession of gang members on the roofs of buildings.
An easy way to obtain the Firefly is to start a Co-Op game with a friend that has it, kill him, pick up the Firefly, and go to a supply point.
You will also get a small amount of Explosives rating by finding a hidden orb. (See "Orb Hunter")