There's only one decent puzzle app that I know of, that's
JiXii. The reason I say it's the only decent one is because it actually creates proper puzzle pieces, rather than just splitting the picture into squares and jumbling them up.
What's the reason for wanting to print it piece by piece, though? I would print the whole picture with the outlines, glue it onto some card or plywood, and cut out the pieces with a saw.