http://www.gatsby.ucl.ac.uk/~zoubin/course05/BayesBall.pdf

Amusing name, linear time algorithm. Also amusingly I happen to have direct line of sight on the author while writing this post :).

In some sense, we know a priori that d-separation has to be linear time because it is a slightly fancy graph traversal. If you don't like Bayes Ball, you can use the moralization algorithm due to Lauritzen (described here:

http://www.stats.ox.ac.uk/~steffen/teaching/grad/graphicalmodels.pdf

see slide titled "alternative equivalent separation"), which is slightly harder to follow for an unaided human, but which has a very simple implementation (which reduces to a simple DFS traversal of an undirected graph you construct).

edit: fixed links, hopefully.