Мария Карповна Байда родилась 1 февраля 1922 года в селе Новосельское Ак-Мечетского района Крымской АССР, РСФСР (ныне Черноморский район Автономной Республики Крым, Украина), в крестьянской семье. Русская. Член ВКП(б)/КПСС с 1951 года. Окончила неполную среднюю школу № 1 в городе Джанкой в 1936 году. Работала в совхозе, в больнице, затем в кооперативе села Воинка Красноперекопского района Крыма.
В Красной Армии с 1941 года. Окончила курсы медицинских сестёр.
В боях Великой Отечественной войны с сентября 1941 года. Санинструктор 514-го стрелкового полка (172-я стрелковая дивизия, Приморская армия, Северо-Кавказский фронт) старший сержант Байда в одном из боёв за Севастополь в мае 1942 года освободила из плена советского командира и нескольких бойцов, уничтожив из автомата 15 солдат противника и четверым раскроила черепа прикладом автомата.
Звание Героя Советского Союза присвоено 20 июня 1942 года.
Попав в плен, держалась мужественно и стойко. Прошла концлагеря Славут, Равенсбрюк. В Австрии удалось перебраться в лагерь для гражданских лиц. Работала на лесоповале в Австрийских Альпах. По доносу была арестована гестапо. Освобождена из гестапо американскими войсками 8 мая 1945 года.
После войны была демобилизована.
Работала заведующей отделом ЗАГС Севастопольского горисполкома, за 28 лет работы она дала напутствия и вручила свидетельства о регистрации браков примерно 60 000 молодых пар, зарегистрировала более 70 000 новорожденных. Неоднократно избиралась депутатом городского совета.
Умерла 30 августа 2002 года. Похоронена на Кладбище коммунаров.