Let me roughly translate those words into English. My English is not fluent enough, so the translation may be awkward or have different nuance. Please correct the sentences if so. The following is my opinion and may not be correct.
- 매우(very): far beyond being normal
- 아주(very): hard to reverse the situation to be normal, sometimes used as 'completely'
- 너무(too): can also be used as 'so'
- 무척(incomparably): not compared to be normal
매우 and 아주 can be used interchangeably in most cases, but there are exceptions when 아주 is used as completely.
꼬마들이 기계를 아주 망가뜨려 버렸다.
Kids destroyed the machine completely.
Some people claim that 너무 contains a negative meaning and should be used as 'too' in English, but most people don't care about it. If you are worried, it's good to use 정말(really) which can be used everywhere.
무척 is used in spoken Korean, though it might be rare. It's used in a relatively formal conversation.
무척 바쁘실텐데 방문해 주셔서 감사합니다.
I appreciate your visit despite being extremely busy.
I guess the frequency used in spoken Korean would be as follows.
정말 >= 너무 > 아주 > 매우 > 무척