When 1,000 joules of coal is burned it only produces 500 joules of electricity. What happened to the other 500 joules of energy?

The law of conservation of energy state that energy can't be destroyed but it doesn't mean the machine to convert it all into desired energy.

In a coal plant, the coal is burned to convert its chemical energy into electrical energy. Some of the energy will be converted into side product like the thermal energy of the gas that appears on the chimney or the friction produced by turbines.

In this case, the coal plants have 50% efficiency because it can extract 500 joules of electricity from 1,000 joules worth of coal.