When Fredo and the Don stop to buy fruit at that little shop in The Godfather, it seems like a spur-of-the-moment decision, and not like Paulie could have known it in advance. I suppose it theoretically could have been a shop the Don visited frequently, but I'm still wondering if Paulie maybe did anything else to "sell out" the Don that was implied somehow and I just missed it.
TL;DR. "What exactly did Paulie do to "sell out" Don Corleone?" He gave them information about Vito Corleone's daily journeys, and about the protection he had, so the gunmen could choose the best place to carry the assassination.
It was all set-up. The assassination attempt is simultaneous to some other attacks on the family.
- killing the Don is cutting the head of the monster, to try and leave the family distressed and helpless.
- killing of Luca Brasi (the most feared hitman of the family) weakens the retaliation power of the family.
- leaving the unwise, violent and impulsive older son in charge weakens the family even more.
Points #1 and #3, to Sollozzo, are the best way to get his drugs deal offer accepted, as Sonny was the only one interested by it during the meeting, when Vito refuses it. Sonny is hotheaded but not stupid.
Talking to the Consigliere is the ultimate move: they want to take advantage of the family, with as little damage and as little blood spilled as possible. Only because Vito refused Sollozzo's offer the killings began.
When you set-up such an massive attack on a powerful opponent, you watch for days, spy on them, follow them, and wait for the best opportunity. Tattaglia (Barzini...) and Sollozzo had everything ready if Corleone was to refuse their deal, which he did, sealing the attack.
The shooting appears to be in Little Italy, where everybody knows the Don, and the family (wrongly) allegedly thought no one would dare attacking them. Makes things easier for 2 Italian mobs to go unnoticed, as they did when coming to the food stand.
Whether Paulie did sell them on this particular day is almost a detail, as he could/did help behind the scene, but his goal is to be AW(ith)OL so he does not appear as guilty, and is not wounded or dead during the shooting. That's also why he had already called sick many times before. Beside that, he's also a bodyguard, so calling sick at the last minute leaves Fredo on his own, and his father without protection.
How did they figure out that Paulie betrayed them? They had some people working for the telephone companies on their own payroll. Some of their own men were wired and tapped. There were phone calls from a booth outside Vito's office, and the family tracked it down to Paulie calling a certain number that would loop to the Barzini camp.
I can't check the book for more accurate references like chapters or page numbers but here are some excerpts about Paulie.
Paulie was the Don's driver and bodyguard. He called in sick on the day Sollozzo's men were to attack Don — so that he gets guarded by useless Fredo only. A deleted scene conveys that Paulie was repeatedly contacted by phone when "sick" at home — presumably to coordinate the day/moment when he will not be driving Don.
The assassins would have been just following Don and choosing a good moment for the attack. Once Don was out of the car alone on the street, that was it.