While it might seem like overkill, I'd go with Cat6 too.
Wired routers are cheap and most wireless routers have multiple RJ45 outlets.
Plates and crimp tools have been covered previously.
Just go for it.
The entire project is easier than you think.
Most of my home connections are hardwired too.
