There's an example in the flatten function documentation of one pattern for flattening a nested structure like this to produce a collection that has one element per nested object.

Adapting that example to this GitHub situation would look something like this:

variable "users" {
  type = set(object({
    username = string
    role     = string
    teams    = set(string)
  }))
}

locals {
  user_team_memberships = flatten([
    for u in var.users : [
      for t_id in u.teams : {
        username = u.username
        team_id  = t_id
      }
    ]
  ])
}

resource "github_membership" "users" {
  for_each = { for u in var.users : u.username => u }

  username = each.value.username
  role     = each.value.role
}

resource "github_team_membership "users" {
  for_each   = { for ut in local.user_team_memberships : "${ut.username}/${ut.team_id}" => ut }
  depends_on = [github_membership.users] # can't create team memberships until org memberships are assigned

  username = each.value.username
  team_id  = each.value.team_id
}

The above will result in membership instances with addresses like github_membership.users["user1"] and team membership instances with addresses like github_team_membership.users["user1/123456"].

One thing I'm not sure about, since I've not worked with the GitHub provider for a while: github_membership resources trigger an asynchronous invitation process where the user must see a notification and accept the invitation. I'm not sure if the github_team_membership create can complete successfully before the invitation is accepted; if not, the above would presumably fail each time a new user is added unless they are initially added with no teams and then assigned teams only after the invitation is accepted. Hopefully that's not the case, though!