Gemara

Yochanan Kohen Gadol sent messengers throughout Eretz Yisrael and found that many people separated only Terumah Gedolah (but not Ma'aseros, so he decreed about Demai). Therefore, Demai is exempt from Terumah Gedolah;

It is exempt from Ma'aser Rishon and Ma'aser Oni, for ha'Motzi mi'Chavero Alav ha'Re'ayah (perhaps the seller already tithed it).

Demai 4:3 (Mishnah - R. Eliezer): When tithing Demai, one need not be Korei Shem to Ma'aser Oni;

Chachamim say, he must be Korei Shem, but he need not physically separate it.

Rishonim

Rambam (Hilchos Ma'aser 9:1): Beis Din ha'Gadol found that everyone separated Terumah Gedolah, but Amei ha'Aretz did not separate Ma'aser Rishon, Sheni or Oni. Beis Din decreed that produce of an Am ha'Aretz is a Safek, the Am ha'Aretz is not believed about it.

Ri Korkus (1): Amei ha'Aretz separate Terumah Gedolah because any amount suffices, and they knew that there is Misah for Tevel to Terumah Gedolah. They did not separate Terumas Ma'aser because this requires separating a significant amount, i.e. a tenth for Ma'aser Rishon. Also, they did not know that there is Misah for Tevel to Terumas Ma'aser.

Rambam (2): One need separate only Terumas Ma'aser and Ma'aser Sheni. They required separating Terumas Ma'aser, for there is Misah (biYedei Shomayim) for anyone to eat produce Tevel to Terumas Ma'aser. They required separating Ma'aser Sheni, for this causes no loss to the owner (he eats it in Yerushalayim). He need not separate Ma'aser Rishon or Ma'aser Oni, for we are unsure whether or not they were already separated; ha'Motzi mi'Chavero Alav ha'Re'ayah, i.e. the Levi or Oni cannot force him to give without proof that these tithes were not separated.

Rambam (3): Even though he need not physically separate Ma'aser Oni, he must Korei Shem. I.e. he says 'a tenth of what is here is Ma'aser Oni'. This is to 'fix' Ma'aser Sheni (we habituate him to Korei Shem to Ma'aser Oni so he will separate Ma'aser Sheni in years of Ma'aser Sheni).

Rambam (ibid. 4): We do not bless on tithing Demai, for it is a Safek.

Rebuttal (Ra'avad Sukah 6:13): Rava says that we do not bless on tithing Demai because most Amei ha'Aretz tithe. If not for this, we would bless because it is a Safek mid'Oraisa.

Defense (Magid Mishnah Sukah 6:13): Abaye (Shabbos 23a) says that we do not bless on tithing Demai because it is a Safek. The Rambam understands that Rava agrees that we do not bless on a Safek; he merely teaches that Demai is not considered a Safek.

Kesef Mishneh (Milah 3:6): We bless only where Chachamim enacted to bless. We do not bless mi'Safek, even regarding Mitzvos mid'Oraisa!

Rambam (ibid. 5): To Ma'aser Demai, he puts 1% of the produce on the side and says that it is Ma'aser (Rishon), and the rest of the Ma'aser is near it. He then makes the first 1% Terumas Ma'aser on the Ma'aser and gives it to a Kohen; one may not separate Terumas Ma'aser before Ma'aser l'Chatchilah.

Source: Mishnah Demai (5:1).

Question: Regarding Terumas Ma'aser we should say ha'Motzi mi'Chavero Alav ha'Re'ayah, and let him sell it to a Kohen! The Yerushalmi implies that one may do so regarding Safek Chalah (Mishneh l'Melech 2). The Tur indeed allows this!

Answer #1 (Ri Korkus, Mishneh l'Melech, ibid.): Rashi (Sotah 48a DH Mafrish) says that it must be given for free lest the Yisrael come to eat while it is in his house before he finds a buyer. Perhaps we are concerned only regarding Demai because the Yisrael knows that most Amei ha'Aretz tithe, but he would not eat Safek Chalah. Alternatively, the Chiyuv Misah for Terumas Ma'aser is less known than that for Chalah.

Answer #2 (Mishneh l'Melech, ibid.): Tosfos (DH Ma'aser) says that Chachamim enacted to give Terumas Ma'aser for free because it is a small amount (1%) and Terumah is cheap. Chalah is a larger amount (over 4% for a Ba'al ha'Bayis).

Question (Mishneh l'Melech, ibid.): A baker separates about 2% for Chalah - if one buys from an Am ha'Aretz baker, must he give the Chalah and Terumas Ma'aser to a Kohen for free, or may he sell them?

Objection (Mishnah Rishonah Demai 5:1 DH Terumas): Amei ha'Aretz were not suspected of not separating Chalah! Mishnah 5:1 discusses a baker who sold Vadai Tevel. (Note - the Mishneh l'Melech's question may be asked about Safek Chalah, e.g. a baker is unsure if he converted before or after kneading.)

Support (for Rambam, and question against the Tur - R. Akiva Eiger, Demai 1:5): A Beraisa (Bava Kama 115b) says that if a barrel of Tamei Ma'aser of Demai broke, he may make it Terumas Ma'aser on other Tamei Ma'aser of Demai, for in any case the Terumas Ma'aser is useless. However, this is forbidden regarding oil, for it causes a loss to Kohanim (Tamei Terumah oil is useful, it may be burned). If Kohanim must pay (the proper value) for Terumas Ma'aser of Demai, what do they stand to lose?!

Question: Why can't he separate all the Ma'aser at once?

Answer (Radvaz): This would be an admission that it is Tevel, and then he would be obligated to give it to a Levi. Rather, he separates the Shi'ur for Terumas Ma'aser; the designation of the rest of the Ma'aser Rishon is on condition that the Demai is really Tevel.

Chazon Ish (Demai 1:5): The Rambam holds that it is possible to separate Terumas Ma'aser before Ma'aser Rishon (this is explicit in Hilchos Ma'achalos Asuros 10:20), just it is forbidden.

Rambam (ibid. 5,6): Afterwards he separates Ma'aser Sheni. Regarding Demai one may separate Ma'aser Sheni before Ma'aser Rishon; he may specify the location of the Ma'aser Sheni and redeem it onto coins.

Beis Yosef (YD Sof 331 DH u'Mah she'Chosav d'Ma'aser): The Rambam equates Demai to Vadai Tevel regarding Ma'aser Sheni because there is no loss. In the time of the Mikdash it may be eaten; nowadays it may be redeemed onto a Perutah.

Rosh (Nedarim 84b DH v'Chachamim): One must Korei Shem and say that the Ma'aser Oni is in the north or south. This is like Hafrashah.