We've currently got a Windows NLB setup between a couple of 2008 R2 servers. One of them is about to be replaced by new hardware and I'm wondering whether I can safely install Server 2012 on the new box, and have it join the 2008 R2 NLB cluster? Or does NLB require that all machines are running the same OS/NLB version?
You can have servers running server 2008 and up in the same NLB cluster. In fact, the recommended way of upgrading the servers in an NLB cluster is to serially remove each from the cluster, upgrade it, and add it back to the cluster.
That said, if your application works well enough in server 2012 to do that, you should consider upgrading the other server to 2012 also for maintainability and general up-to-dateness (there are some significant exploit mitigation advances under the hood in server 2012).