The Gemara in Pesachim 105b states that Birkat Hamazon requires a cup of wine. However, the Gemara didn`t state under what conditions this is necessary.
There are three opinions in the Rishonim regarding this issue:
Tosafot and the Tur think that even an individual who is benching requires a cup of wine. Indeed, according to this opinion, one shouldn`t wash hands for bread if wine isn`t available for Birkat Hamazon.
Midrash Rut Hane`elam holds that a cup of wine is required only when three are benching together – a zimun.
The Rambam (Hilchot Berachot 7, 15) holds that Birkat Hamazon never needs a cup of wine. (Apparently the Gemara according to the Rambam didn`t mean to be binding.)
The Shulchan Aruch (Orach Chayim 182, 1) brings all three opinions as “Yesh Omrim”s` – “Some say”. The Mishna Berura therefore wrote that the Mechaber didn`t decide which opinion is correct. (Although according to the general understanding of the Shulchan Aruch, whenever he brings several opinions as “Yesh Omrim”, he prefers the last one, in which case here he would hold like the Rambam.)
The Ran, quoted by the Rama (ibid), says that according to all opinions, it is nevertheless a “mitzvah min hamuvchar” – a good thing, to bench over a cup of wine.
The Mishna Berura mentions that today most people don`t say Birkat Hamazon over wine, unless wine is readily available. Maybe this is how the minhag developed to use wine at benching only on Shabbat – when indeed wine is already at the table because of Kiddush.
It is interesting that although many insist that a cup of wine is required only when there is a zimun of ten, there is no source for this. Maybe this custom evolved from the inherent importance such a zimun has.