Cedar is tough because of the tannins in the wood... but check around with the paint manufacturers web sites and I think you will find products for cedar. As you have indicated, primer is VERY important.
Suggesions: Olympic paints/stains, Behr, Flood, .. these are most typical in wood coatings, but Sherwin Williams, Duron, Zinnser, etc probably have coatings as well that would be good primer.