I've got schools with both part approvals in my area. I'm just interested in recreational flying, I'm not sure which part is more suited to my needs.
What are the differences I should consider before choosing one or the other?
There's no singular right answer, it's up to the individual and how he or she learns best. The biggest difference between the two you'll find is that part 141 schools are always very structured in their training regiment. That is not to say part 61 isn't (nor does it imply that it's better for everyone), it's just that part 61 does things according to what they wish with less FAA oversight.
You might know that under part 141, the earliest you can get your ticket is 35 hours, while part 61 requires a minimum of 40 hours. Don't let that red herring influence you; almost everyone takes more than 40 hours regardless of the school type.
I did my training at a Part 61 school, but we followed Jeppesen's Part 141 syllabus. So the differences can be minimal if choose that route.
Not relevant to Private Pilot training, but an important difference between Part 61 and Part 141, when it comes to Instrument training, is that Part 61 requires 50 hours of PIC cross-country, whereas Part 141 does not.
When I wanted to start my instrument rating, I only had 25 hours PIC cross-country, so Part 141 sounded appealing to me. Having recently moved to New York City and not knowing anyone in aviation here, I called the owner of a Part 141 school, and immediately disliked him. He was arrogant and egotistical and didn't care about anything I had to say. He just wanted to brag about his airline experience and how organized his school is... then didn't even call me back at the time he said he would. So I called up another flight school and immediately liked them and went flying with them the same week. Unfortunately they're only a Part 61 school, but the fact that I like them is a big win.
The point is, the biggest difference between any two schools is not actually 61 vs. 141, it's the people who run it, and whether or not you mesh with them. Unless you have commercial ambitions (where Part 141 might help get you where you're going faster), base your decision on the people, not the part.