There two excellent parodies contain either the phrase "Klingons on the starboard bow" or "Klingons off the starboard bow". How many times, if ever, did this exact phrase occur in The Original Series? I can't help but wonder if, like "beam me up Scotty", it was zero.
There are actually two questions here. I shall take them in order.
How many times is the literal phrase "Klingons on [or off] the starboard bow" spoken in Star Trek: The Original Series?
Zero. There is, however a single mention of the ship's "starboard bow" in TOS: Charlie X where we're told:
UHURA: Sir, something off our starboard bow. The message says they're from Thasus.
This is close enough that it could be the trope originator.
How many times were there actually Klingons on the ship's starboard bow?
At least once in the TV series. In TOS: Elaan of Troyius a Klingon ship is sighted on a parallel bearing of
"mark seven three point five"
which would place it on the ship's starboard bow.