First i'm going to start by saying, i do have decent knowledge on how these puzzles do work.

The question i'm here to ask is, How can i begin? (As suggested by the title..)

I'm wondering what program i should use to begin creating a design for my own custom puzzle, and preferably one that is compatibal with shapeways.

If any of you can help me out, that would be great! Thanks!

Welcome to TP forums. Have you read the FAQ? Have you tried searching the forums, reading a few threads, looking through the Museum try searching anything by Tomz, Oskar, wwwmwww, David Pitcher, Tony Fisher etc. etc. Buy some puzzles and take them apart, that will give you a good idea about how they work.

There currently is an active thread on FreeCAD with links to YouTube video instructions.

Any Software able to turn models into STL files you can use for Shapeways. We know of people here using SolidWorks for instance.
But AutoDesk (AutoCAD), ProEngineer, CATIA etc. etc. will do the job also (professionally).

Would it be possible to use blender for this? (3d modeling software)

Blender is designed for art more that for mechanical engineering. Others have found Blender too limiting to be useful for even moderately complex puzzle design.

NO
Trust me, don't waste your time on it.

Thanks for telling me.