Fortunately the guys at react/Facebook are well aware of this and built in a provision to help developers with this problem:
The basic premise around using this method in relation to SEO is that you build your initial interface on the server side and display it when a http request hits your website. You then initiate the client side rendering of the same react component into the containing division once the page has loaded. React will then attach event handlers to take control of the content displayed.
I also asked about it and Ben Alpert - one of the guys working on react pointed me in the direction of v8js.
Stoyan gives a good overview of how one can setup react with v8js. This was my starting point when setting things up. Of course to deploy a production ready site using such a setup there are certainly a lot of additional considerations. Furthermore the v8js php extension is complex in nature and there is not much in the way of documentation or tutorials.
A few issues that I encountered were:
I currently have one of my websites running in production with such a setup. It was a complex initial setup, but working with it once you are set up is an absolute pleasure. My site is being indexed.. so it works, and I have a beautiful client facing react interface.
I went down the line of setting this up to work with PHP. It is however perfectly possible to implement a similarly premised setup with any codebase. Pete Hunt (another member of the react team) mentions here how Instagram uses a combination of node and python.