The chip is probably bad now. What most likely caused it to become bad was not having all of the input pins connected to either a Logic HI or Logic LO level in conjunction with a beefy power supply.
If your power supply had been current-limited to a few mA, no damage would likely have occurred.
If you have any more of those chips available, try using 10k resistors from each input pin to Ground. The output pins should all be HI (Vdd) and the chip should be running very cool - the quiescent current consumption is very low micro Amps.
If you confirm this to be the case, it means that you most likely have everything wired correctly. Now substitute the first chip that you were using (the one that got very hot). If it now runs cool and the output pins are reading the correct voltages, there is a good chance that the chip is still good.
To confirm that the chip is in fact good, use 1k resistors to pull each pair of input pins to Vdd. When both pins for one gate are HI, the output should go LO.
There is a good reason for using the resistor values that I mention. 10k is a reasonable pull-up resistor (0.5 mA); 1k is a stiff pull-down (5 mA). If you get either resistor connected to an output instead of an input, no damage will occur.
Additionally, the two resistors (10k pull-down, 1k pull-up) forms a voltage divider that puts the pin at about 4.5 Vdc. This is considered to be a logic HI whether the chip has TTL-compatible inputs or CMOS (symmetrical threshold) inputs.