In a Newton's Cradle, ideal balls are made out of a material that is very elastic and of uniform density. Elasticity is the measure of a material's ability to deform and then return to its original shape without losing energy; very elastic materials lose little energy, inelastic materials lose more energy. A Newton's cradle will move for longer with balls made of a more elastic material. A good rule of thumb is that the better something bounces, the higher its elasticity.
Stainless steel is a common material for Newton's cradle balls because it's both highly elastic and relatively cheap. Other elastic metals like titanium would also work well, but are rather expensive.
It may not look like the balls in the cradle deform very much on impact. That's true -- they don't. A stainless steel ball may only compress by a few microns when it's hit by another ball, but the cradle still functions because steel rebounds without losing much energy.
The density of the balls should be the same to ensure that energy is transferred through them with as little interference as possible. Changing the density of a material will change the way energy is transferred through it. Consider the transmission of vibration through air and through steel; because steel is much denser than air, the vibration will carry farther through steel than it will through air, given that the same amount of energy is applied in the beginning. So, if a Newton's cradle ball is, for example, more dense on one side than the other, the energy it transfers out the less-dense side might be different from the energy it received on the more-dense side, with the difference lost to friction.
Other types of balls commonly used in Newton's cradles, particularly ones meant more for demonstration than display, are billiard balls and bowling balls, both of which are made of various types of very hard resins.