At what stage of computer science PhD should you start looking for post-doc?
Around your last year.

So much of this comes from networking though, so it is important to be meeting people at conferences long before you are about to graduate. 

In the US, many postdoc positions are filled quite late (often after faculty offers have gone out, so mid to late Spring, maybe even early Summer) but you should start talking to potential postdoc advisors maybe a year before your graduation to put a bug in their ear.