If you've just started here's the location of all the Crimson Spheres.
I finished my first game at 74% and found that I had missed tons of the game!
If you find all 10 Crimson Spheres you'll be able to enter the Den of the Woe and get more completion points, (be warned - you must be able to withstand 5,000 hit to all 3 girls at once.)
Also this is the best way to learn about Paine, ('cuz she's sure not going to tell you.)
Anwayz, to locations, Most of the Crimson Spheres you only get ONE chance to get the entire game.
I'll list them in game order.
Ch.1, After (or during-whichever you prefer) the foggy fiend mission on Mushroom Rock Road, return and follow the path down to the Den of the Woe, you will automatically pick of Crimson Sphere 9, which shows as Crimson Report 1 on Shinra's list.
Ch.2 Again, return to the Den of Woe, you will be given Crimson Sphere 7
Ch.2 Crimson Sphere 10 is in Logo's room, (part of the story I believe, if not the room has purple doors, and it shows as Crimson Report 2 on Shinra's list.)
Ch.3 Go to Guadosalam speak with a few people, when finished go to the "circle " bedroom. You'll find it hidden up top. Crimson Sphere 4, (I believe that this is the only one that you more that one shot to get.)
Ch.3, When Djose is a hotspot, GO TO BEVELLE, follow who you see underground, (you'll need to lower the lift again) and then after scenes, you'll need to pick up the sphere on the floor. Crimson Sphere 1
At the End of Ch. 3 Crimson Sphere 2 & 3 are given to you.
Ch. 4 after the concert go to the engine room and LeBlanc will give you Crimson Sphere 5. (You will be told she is there as long as you don't skip the scene.)
In Ch. 5 Crimson Sphere 6 is in Bevelle on Floor 1. Crimson Sphere 8 is on Floor 20.
I do not recommend going past here for now, you can make it to 40 with no probs, but until your much, much stronger you won't stand a chance any further. And you Can exit the dungeon, but you'll have to start over on your current floor.