Ordinary Israeli fruit and vegetable stands do not carry teudah. Does the Israeli government ensure terumot and maasrot are taken at some point? For example, can one taste produce in Machane Yehuda or one must take the produce home and separate the various portions first?
No, the government does not ensure that terumot and maasrot are taken. Stands with a teudah are ensured by the Rabbanut.
I read in a guide for Anglos in Israel that in a case such as this where there is a doubt if the produce had been tithed, the tithes should be separated (again) without the accompanying blessings.
As for tasting food at a shuk, I've never really thought about that. I don't think it is halachically achilat arai (a snack), as the fruit is already chayav in trumot and maasrot. Therefore, it seems to me that you shouldn't do it unless you know that they have been taken off, and you have permission from the store owner.