All Clerics MUST have a patron deity, and a Cleric's Domains MUST appear on their patron deity's list of Domains. In other words, you may not have a Domain ability that your patron deity does not have, and as a Cleric you may not be "faithless". It is therefore advised that you check the list of available deities before you make a Cleric, find one you like, and select your Domains appropriately.
Another restriction Clerics have regarding patron deities is their alignment. A Cleric's alignment must be within "one step" of their deity's. Also, it can only be different from their deity's in one aspect. For example, Obad-Hai is True Neutral, therefore, his Clerics can be any of the following alignments: Neutral Good, Chaotic Neutral, True Neutral, Neutral Evil or Lawful Neutral. No other alignments are allowed for a Cleric of Obad-Hai, since all other alignments are more than one step away or would require being different in more than one aspect.
Note that some deities have additional restrictions for their follower's alignments (e.g. St. Cuthbert has no Evil followers, even though Lawful Evil is within one step of his alignment.)