In Australia it varies by state. Only Queensland and the Northern Territory celebrate the early May Labour Day (and the NT calls it "May Day" rather than "Labour Day"). On the 1st of the month, but the first Monday in May.

I think other states have it at different times for a variety of reasons. Part of it is a deliberate effort to disempower the day from its international meaning. But it's also about spreading out public holidays. After two public holidays for Easter in late March/early April and ANZAC Day on 25th April, Labour Day being the first week of May is a lot of public holidays in a very short time.