Depends on the usage of the logo. If you just want a small graphic to place on the header/banner of a website site, then Photoshop will do just fine. But if you will need to scale it from very small all the way up to poster or billboard size and everything in between, I suggest Illustrator.
Photoshop is primarily a raster-based program, which means it works in pixels. Pixels do not scale very well, as a massive reduction or enlargement will require a change in the number of pixels in order to maintain resolution similar to the original image.
Illustrator is vector-based, which means it works with contiguous shapes, or vectors. These vectors have the flexibility of scaling to any size without degrading the image's resolution.
If you do not have access to Illustrator, you can revert back to Photoshop.
1. You will need to start by opening a very large canvas, possibly 10000x10000px. I am unsure if a standard 72 dpi will need to be changed at this point (or whatever your default setting is).
2. Create your individual shapes using the Pen tool to fill as much of the canvas as possible.
3. Save each shape as a Custom Shape. This way, you can have access to them at anytime without having to recreate them from scratch.
4. After drawing out each shape and filling with the color of your choice, save the shape (or combination of shapes) as a Smart Object. This way, you can scale the object down or back up to original scale with no noticeable loss in resolution.