How is $Nb$ (number of columns) calculated in AES (Rijndael)?

The NIST publication for AES defines $Nb$ as:

Number of columns (32-bit words) comprising the State. For this standard, Nb = 4.

In Section 5.2: Key Expansion, $Nb$ has been used to calculate the number of round keys to be generated.

Section 6.3 states:

This standard explicitly defines the allowed values for the key length (Nk), block size (Nb), and number of rounds (Nr) – see Fig. 4. However, future reaffirmations of this standard could include changes or additions to the allowed values for those parameters. Therefore, implementers may choose to design their AES implementations with future flexibility in mind.

It is apparent that that $Nk$ is the length of the key in terms of 4-byte words, so it can be calculated as: $$ Nk = {(Key Size) \over (Bits Per Byte) * (Bytes Per Word)} $$ where,

$$ Bits Per Byte = 8 $$

$$ Bytes Per Word = 4 $$

Hence, it will be 4, 6 and 8 for 128, 192 and 256 bit keys respectively. And $Nr$ (number of rounds) is: $$ Nr = (Nk) + 6 $$

Similarly, is there an explicit formula to calculate $Nb$ or is it a constant value ($4$) that also remains the same for potentially higher length keys like AES-512?

$N_b$ is fixed, as mentioned in many parts of FIPS standard for AES.

The only stipulation is, as you note, that implementers may keep future changes in mind.

The AES state (for all variations) is 128 bits or 16 bytes, which is initialized to the plaintext or ciphertext (depending on whether one is encrypting or decrypting). For the purposes of visualization, these 16 bytes are arranged in a $4\times4$ grid (column major).

The constituents of the round function act on this state. In particular shiftRows and mixColumns act on the $4\times4$ array in ways suggested by the names, while subBytes and addRoundKey act on the individual bytes of the array, the latter in a key-dependent way. (Similarly for the inverse functions in decryption.)

In any case, the number of columns is 4 for all variations of AES. What changes between the versions of AES is the key size, key schedule, and the number of rounds.