From all accounts, Gloucester was a staunch Protestant (probably having something to do with the fact that he spent his formative childhood years in the captivity of the Parliamentarians). In fact, his religious views were strong enough to cause a permanent falling out with his own mother after his release into exile in France, largely because of her Catholicism. Actually, his friendship with Le Grand Condé at the French court had a lot to do with the Condé's sympathy for the Huguenots. So, given Gloucester's character, it's not too great of a leap to assume that he'd either insist upon a Protestant bride or be rather firm about Condé's niece's conversion (who I believe was one of the daughter's of the Duchesse de Longueville), which will probably prevent the marriage from happening given the attitudes at the French court.
Assuming he marries at some point between 1661-1665, the political climate in England also will probably prevent a Catholic marriage, given how Charles' Portuguese match wasn't initially very popular. The King is far too clever to provoke his Parliament this early in his reign with a Catholic marriage his brother doesn't even want in the first place. And, given the
mesalliance that was contracted by his brother and Anne Hyde, I doubt he'll be able to marry for love either.
As for who are good candidates, given the previous patterns of the Stuarts and the OTL examples of Anne and Mary, I'd agree with what's been already said: a Danish princess or a Dutch match with the Orange-Nassau family is a good bet.
If he marries a bit later (in the late 1660's or early 1670's) there's also his cousin,
Liselotte, to consider--and the possibilities there are fascinating, given her character...and the bitchy memoires we could end up with about the Court of the Merry Monarch