From what I understand, your table uf has the geom of the federal units and municipios the geom of the municipalities, and you don't hvae any problem with the polygons (usually when you do this kind of things, the geom are not perfectly similar and there is approximation that make the correspondance between 2 tables difficult, but here I assume they come from the same source or have been cleaned before with something like a snaptogrid and other).
In this case, you are sure that your municipalities are completely inside your units, so I don't see any reason the request you did doesn't work. The st_intersects is not necesseray however. To make it clearer, I would write it like that:
SELECT uf.gid, ST_Union(geom)
FROM (
SELECT uf.gid, m.geom FROM municipios as m LEFT JOIN uf ON st_contains(uf.geom, m.geom)
) as req
GROUP BY uf.gid
If you have problem with geom that shouldn't be here, maybe you can give us an exemple?
And in case your geom are not from the same sources and not perfectly aligned, you will have cases where the municipality can be slightly outside the uf, so instead of st_contain you would need to use st_intersection with all the uf (where st_intersect), order them by st_area and take the first, to get the uf where the municipality is the most, so it's a different story...