When I did my pro-brewer gig we had mash paddles made out of red oak since it is a pretty good hardwood. However, the high temps in the mash tun eventually spread the fibers of the wood weakening it and I made several trips to get it repaired or remade. A lot of others use boat oars and they seem to hold up (I think they are maple), but unless they are canoe oars, they might be a bit too big for home use.
My paddle that I have at home is made of maple and I agree with others, it probably the best wood to use. Again, no finishes or oils at all on the paddle.