My wife and I have decided we're going to homeschool our son, almost five, for various reasons.

You might want to look into the idea of unschooling.

My wife and I have decided we're going to homeschool our son, almost five, for various reasons. What age do you think it would be appropriate to start rationality training, and how would you go about it?

Certainly before they reach five.

(1) Kids want parents to do stuff. Most parents rely on their authority and don't give their kid what it wants, even if the kid is able to provide valid reasons. A good way to teach rationality is to avoid to rely on arguments by authority.

My father had the policy of always giving me the real reason when I asked for something whether or not I would be able to fully understand the answer. That taught me that it's okay to get answers to questions that I don't understand. It was a valuable lesson for me.

Dumbing things down and relying on authority for arguments are the two biggest things that parents do to avoid their children being rational.

(2) When it comes to giving out pocket money consider giving it out as betting money. Let's say the allowance is $3 per week. Whenever the kid disagrees with you about a factual matter, he's allowed to ask you for your odds.

So the kid thinks it's raining. You don't think so and are pretty certain. So you say you have 4:1 odds. The kid can bet $1 from his betting money. If he wins the bet than he get $4 in real coins from which he can buy something.

The pocket money is motivating so he will have a huge incentive to get good at having accurate confidence in his beliefs. After a while he might even give you some rationality lessons.

(3) I would think about teaching a five year old Anki for all occasions where he has to learn something.