Stones:
Water Stone - Surf to the lighthouse in the 5th gym's city (the ground one).
Dusk Stone - There's a Dusk Stone in the Cave where you encounter Kibagos and the blue one of this legendary Fighting-Dogs.
The cave is on Route 6, near to this electric cave. You need to go to the house on Route 6 and then behind it right to a river. Surf it along past the stones and you will find this cave. But one of your Pokemon needs to know Flash (TM 70).
Fire Stone - Go to the very right of the city (Hiun City), where the gateway to the bridge is, then go down the stairs and there's a scientist at the dock. Talk to him, and he lets you choose one of three stones.
The Fire Stone is the second option. Another Method - In the desert, there is a fire stone.
Leaf Stone -
Moon Stone - You get the Moon Stone from Aloe after helping get the head back.
Hard Stone - Upstairs in Shaga's house, a football player gives you a Hard Stone.
Thunder Stone - Go to the All Nine Shopping Mall on Route 9. An NPC on the top floor also gives you a Thunder Stone for free.
I started making a stone list. It's not completed, yet. Post where you find the stones (please be specific) and I'll add it to the list on the front page.