Question: And when did it start being used that way? Before or after the bird meaning of "rook"?

Answer: 
[etymonline.com](http://www.etymonline.com/index.php?term=rook)

> 
> "chess piece," c.1300, from O.Fr. roc,
>  from Arabic rukhkh, from Pers. rukh,
>  of unknown meaning, perhaps somehow
>  related to the Indian name for the
>  piece, rut, from Hindi rath "chariot."
> 
> 
> 

According to the OED, the word rook meaning the bird was first used circa 725.

So it seems that the two words have different origins.
In the first case (when the word is used to refer to a chess piece), the origin of the word is Middle English, from Old French *rock*, based on Arabic *ruḵḵ*.  

In the second case, the origin of the word is from Old English *hrōc*.

The word has been first used to refer to the bird, but the two words have different origins.