How to handle many-to-many relationships in a RESTful API?

Make a separate set of /memberships/ resources.

1. REST is about making evolvable systems if nothing else. At this moment, you may only care that a given player is on a given team, but at some point in the future, you will want to annotate that relationship with more data: how long they've been on that team, who referred them to that team, who their coach is/was while on that team, etc etc.
2. REST depends on caching for efficiency, which requires some consideration for cache atomicity and invalidation. If you POST a new entity to /teams/3/players/ that list will be invalidated, but you don't want the alternate URL /players/5/teams/ to remain cached. Yes, different caches will have copies of each list with different ages, and there's not much we can do about that, but we can at least minimize the confusion for the user POST'ing the update by limiting the number of entities we need to invalidate in their client's local cache to one and only one at /memberships/98745 (see Helland's discussion of "alternate indices" in Life beyond Distributed Transactions for a more detailed discussion).
3. You could implement the above 2 points by simply choosing /players/5/teams or /teams/3/players (but not both). Let's assume the former. At some point, however, you will want to reserve /players/5/teams/ for a list of current memberships, and yet be able to refer to past memberships somewhere. Make /players/5/memberships/ a list of hyperlinks to /memberships/{id}/ resources, and then you can add /players/5/past_memberships/ when you like, without having to break everyone's bookmarks for the individual membership resources. This is a general concept; I'm sure you can imagine other similar futures which are more applicable to your specific case.

In a RESTful interface, you can return documents that describe the relationships between resources by encoding those relationships as links. Thus, a team can be said to have a document resource (/team/{id}/players) that is a list of links to players (/player/{id}) on the team, and a player can have a document resource (/player/{id}/teams) that is a list of links to teams that the player is a member of. Nice and symmetric. You can the map operations on that list easily enough, even giving a relationship its own IDs (arguably they'd have two IDs, depending on whether you're thinking about the relationship team-first or player-first) if that makes things easier. The only tricky bit is that you've got to remember to delete the relationship from the other end as well if you delete it from one end, but rigorously handling this by using an underlying data model and then having the REST interface be a view of that model is going to make that easier.

Relationship IDs probably ought to be based on UUIDs or something equally long and random, irrespective of whatever type of IDs you use for teams and players. That will let you use the same UUID as the ID component for each end of the relationship without worrying about collisions (small integers do not have that advantage). If these membership relationships have any properties other than the bare fact that they relate a player and a team in a bidirectional fashion, they should have their own identity that is independent of both players and teams; a GET on the player»team view (/player/{playerID}/teams/{teamID}) could then do an HTTP redirect to the bidirectional view (/memberships/{uuid}).

I recommend writing links in any XML documents you return (if you happen to be producing XML of course) using XLink xlink:href attributes.

I would map such relationship with sub-resources, general design/traversal would then be:

# team resource
/teams/{teamId}

# players resource
/players/{playerId}

# teams/players subresource
/teams/{teamId}/players/{playerId}

In Restful-terms it helps a lot in not thinking of SQL and joins but more into collections, sub-collections and traversal.

Some examples:

# getting player 3 who is on team 1
# or simply checking whether player 3 is on that team (200 vs. 404)
GET /teams/1/players/3

# getting player 3 who is also on team 3
GET /teams/3/players/3

# adding player 3 also to team 2
PUT /teams/2/players/3

# getting all teams of player 3
GET /players/3/teams

# withdraw player 3 from team 1 (appeared drunk before match)
DELETE /teams/1/players/3

# team 1 found a replacement, who is not registered in league yet
POST /players
# from payload you get back the id, now place it officially to team 1
PUT /teams/1/players/44

As you see I don't use POST for placing players to teams but PUT, which handles your n:n relationship of players and teams better.