First of all, there's a VERY precise viewing order recommendation [here][1]. I won't copy/paste it as it basically lists every episode of BOTH shows in order, but it seems to be fairly well thought out.

Also, a full list of Xena crossovers in Hercules episodes [is available][2].

----------------------

Second, there are some required orderings, as listed below. The info is lifted from Yahoo Answers - second one is anonymous so can't attribute, but it had 5 up-votes, first one is from "II.Sσñaя εs gяa†ιs.II" [Yahoo! answer][3]. I re-formatted for clarity.

First, here's a list of Hercules Episodes required to understand subsequent Xena episodes:

 1. Before watching Xena (any of the episodes), watch the pre-history in the following 3 Hercules episodes from S1: "The Warrior Princess" (#9), "The Gaunlet" (#12), "Unchained Heart" (#13). You should also watch the 5 movies as well before watching Xena (and from what I understand before you watch Hercules as well, but that wasn't terribly clear to me as I haven't watched the movies myself):

        Hercules and the Amazon Women (Lucy Lawless)
        Hercules and the Lost Kingdom (Renee O'Connor)
        Hercules and the Circle of Fire
        Hercules and the Underworld
        Hercules and the Maze of the Minotaur

 2. "Surprise" (Hercules, Season 3 Episode 12)  and "Judgement Day" (Hercules, Season 3 Episode 15) - Hera has freed Callisto from Tartarus on the condition that she kills Hercules; but the episodes doesn't have any impact on Xena storyline.

    However, it is impacted by prior events in Xena storyline, and therefore should be watched **after** "Ten Little Warlords" (Xena, Season 2, Episode 8).

 3.  "Stranger in a Strange World" (Herculs Season 4, episode 5) and "Armaggedon I and II" (Hercules Season 4, episodes 13 and 14). 

     You should watch them **after** "Maternal Instincts" (Xena, season 3, episode 11), because

    >! The Armaggedon story starts off right after the funeral of Xena and Gabrielle´s children, so 

 4. The next set of advice is somewhat unclear, but I included it for now and will try to untangle later. I personally don't see any reason to bother with ordering these episodes.
  
   > On to xena S4 and herc S5 - watch Hercules "Faith", "Descent", "Resurrection" first then "Xena" "Adventures in the sin trade" parts 1&2 and "A family affair"

   > Herc's last appearance in Xena's "God Fearing Child"

-------------------------

**I will try to summarize the required orderings:**

 - Hercules S1E9, S1E12, S1E13 and 5 movies before Xena S1E1

 - Xena S2E8 before Hercules S3E12

 - Xena S3E11 before Hercules S4E5


  [1]: http://whooshorg.proboards.com/index.cgi?board=xena&action=display&thread=4646
  [2]: http://www.vidiot.com/Contrib/Xena/htljxover.html
  [3]: http://answers.yahoo.com/question/index?qid=20110907155423AAOML6w