Most of the time, the teams don't actually "move" around, per se. Minor League teams are usually separate corporations from the major league team, and form affiliations with major league teams, via the Player Development Contract. This affiliation allows the Major League team to have control over the players and coaches of the minor league team, but the other elements of the team (the stadium, ticket sales, administrative details, etc.) are managed by the Minor League franchise.
That said, it's certainly possible for a Minor League team to relocate physically (as well as change affiliation, or not) - usually for the same reasons as Major League teams might relocate: attendance, stadium conditions, etc.; and occasionally also as a result of a player development contract - but often not.
MLB.com has a fairly detailed section on the business of Minor League Baseball and covers all of this in much more detail.
In your specific example, the New York Mets ended their relationship with the Norfolk Tide after 2006, and changed to the New Orleans Zephyrs for two years, then the Buffalo Bisons for four, now the Las Vegas 51s since 2013. All of those teams are still in existence, and have relationships with other teams (Buffalo is now the Blue Jays AAA team, for example).
As to how frequently it changes, well, the Mets were affiliated with the Tides, originally the Tidewater Tides (originated 1961, affiliated with NYM in 1969) from 1969 to 1990. The Tides then moved to Norfolk, remaining affiliated with the Mets until 2006; at the time the second longest affiliation between a AAA team and a Major League team (the Atlanta Braves had the longest) at 37 years. They then changed teams three times in less than 10 years. So - certainly it happens from time to time, and 30 years is a "long" time to have a single affiliation. I would say it is a fairly common occurrence overall; most years it seems a couple of teams change at least. My team (the White Sox) hasn't changed any of their main affiliates (Charlotte, Birmingham, Winston-Salem, Kannapolis) since 2001 , but who knows when that might change... and they change their rookie league teams pretty frequently (those are much higher turnover, from what I've seen).