A 4gb card will obviously hold twice as much as a 2gb card. How those sizes translate into numbers of pictures depends on how large the picture files are. Most cameras can shoot at different resolutions, with higher resolutions making for larger files. Some cameras can shoot at different quality levels, with higher quality making for larger files. Some cameras can also shoot in different file formats (typically JPG, the standard for pictures on the Internet, and RAW, the a richer format proprietary to each camera make/model). The size of files also varies somewhat with what you take a picture of and the camera settings, with pictures showing lots of detail or picture taken in low light sometimes making for slightly larger files.
Some camera reviews, like
this one on DPReview for the Canon S5 IS, will give you size approximations. It looks like it will hold about 286 pictures on a 1 gig card at the highest resolution and quality settings. From that, we can do some simple math to see that it would hold about 572 pictures on a 2 gig card and 1,144 pictures on a 4 gig card.
In the past, there were some cameras that had problems using cards larger than 2 gig. I don't know whether that problem has been universally fixed or not.
As a general rule, I don't worry about brands of cards. Others are quite brand loyal. I would suspect that using any major brand (Sandisk, Transcend, Crucial, Lexar, Panasonic, Kodak, Kingston, etc) will all work just fine. In fact, there are probably only a very small number of companies that actually manufacturer the memory cards that supply the brands selling them. I have noticed the casing on some cheaper cards seems a bit flimsier than on others.
There are also large speed differences between cards. The impact of the cards speed depends on a lot on how well the camera can take advantage of the cards speed. I've never really noticed much difference in the speed of the cards I've used, but I suspect that is a function of the camera I use.
As for the type of memory card, there is a frightening variety. Compact Flash (CF) and SD (what is that, Secure Digital?) are the two most common by a wide margin. Sony likes variations of its proprietary memory sticks. There are a bunch of others that I know nothing about like xD cards. As long as your camera takes either CF or SD cards, I wouldn't worry about it. If you are considering a camera that uses something else, check the price and availability of such cards and consider that as a factor when deciding on that camera. At the moment, SD cards appear to be the cheapest, but it was not always the case. I don't know why CF cards cost more and I wouldn't be suprised at all to see them come back to parity.