One of my friends is a member of a BSG website and he's been talking about the contellations for a while now. According to him, the Orion constellation first showed up in the episode where Cally was "ejected" from Galactica... apparently when she was looking out the viewport, you could see Orion then too.
Justin, here's a screen grab from the 'net from that episode...
YOU are a rock star sir. Thanks for sharing! I think its awesome that they're including this kind of detail in the show.