Star Pieces are found when stars fall to the ground. When a star falls, it makes a very loud "falling" sound (a drawn-out 'wheee' that lowers in pitch) and a crash when it lands; they will then be apparent from a distance by bright rays of light.
The block that the Star crashes into will not suffer any damage, despite the explosion-like sound that it plays. However, mobs do receive damage from stars.
Walking over the fallen star soon after it lands will give you a star piece and Experiences, depending on how fast the player 'takes' the star. 9 star pieces can be crafted into a Starstone and some experience. Roughly one star falls every night. However, in multiplayer, there is usually more star falls every night, depending on the amount of players online.
Stars cannot be "extinguished" by falling into water – they can still be collected.
If the star piece is left for a few seconds and still retrieved before it disappears, it will only give you Stardust and a few experience orbs around it.