Decrease evenly means to spread out the decreases across the row so that they're approximately equally spaced. So for 64sts you would decrease about every 8 sts (for example, knit 6, knit 2tog, knit 6, knit 2tog etc).
You can work it on straight needles. It's written to seam the hat at the end. You can always knit back and forth on circular needles, too. The circs aren't only for knitting tubes.