TypeVar and NewType seem related but I'm not sure when I'm supposed to use each or what the difference is at runtime and statically.

The two concepts aren't related any more than any other type-related concepts.

In short, a TypeVar is a variable you can use in type signatures so you can refer to the same unspecified type more than once, while a NewType is used to tell the type checker that some values should be treated as their own type.

Type Variables

To simplify, type variables let you refer to the same type more than once without specifying exactly which type it is.

In a definition, a single type variable always takes the same value.

# (This code will type check, but it won't run.)
from typing import TypeVar, Generic

# Two type variables, named T and R
T = TypeVar('T')
R = TypeVar('R')

# Put in a list of Ts and get out one T
def get_one(x: list[T]) -> T: ...

# Put in a T and an R, get back an R and a T
def swap(x: T, y: R) -> tuple[R, T]:
    return y, x

# A simple generic class that holds a value of type T
class ValueHolder(Generic[T]):
    def __init__(self, value: T):
        self.value = value
    def get(self) -> T:
        return self.value

x: ValueHolder[int] = ValueHolder(123)
y: ValueHolder[str] = ValueHolder('abc')

Without type variables, there wouldn't be a good way to declare the type of get_one or ValueHolder.get.

There are a few other options on TypeVar. You can restrict the possible values by passing in more types (e.g. TypeVar(name, int, str)), or you can give an upper bound so every value of the type variable must be a subtype of that type (e.g. TypeVar(name, bound=int)).

Additionally, you can decide whether a type variable is covariant, contravariant, or neither when you declare it. This essentially decides when subclasses or superclasses can be used in place of a generic type. PEP 484 describes these concepts in more detail, and refers to additional resources.

Addendum: Python 3.12 generic parameter lists

Starting in Python 3.12, the following syntax has been available to declare type variables.

def get_one[T](x: list[T]) -> T: ...

def swap[T, R](x: T, y: R) -> tuple[R, T]: ...

class ValueHolder[T]:
    def __init__(self, value: T): ...
    def get(self) -> T: ...

These declarations are equivalent to those above, but now the type variables are only defined in type signatures within their functions/classes, rather than being stored in regular Python variables. The Python 3.12 release notes contain a summary, as well as links to more-detailed documentation.

NewType

A NewType is for when you want to declare a distinct type without actually doing the work of creating a new type or worry about the overhead of creating new class instances.

In the type checker, NewType('Name', int) creates a subclass of int named "Name."

At runtime, NewType('Name', int) is not a class at all; it is actually the identity function, so x is NewType('Name', int)(x) is always true.

from typing import NewType

UserId = NewType('UserId', int)

def get_user(x: UserId): ...

get_user(UserId(123456)) # this is fine
get_user(123456) # that's an int, not a UserId

UserId(123456) + 123456 # fine, because UserId is a subclass of int

To the type checker, UserId looks something like this:

class UserId(int): pass

But at runtime, UserId is basically just this:

def UserId(x): return x

There's almost nothing more than that to a NewType at runtime. In Python 3.8.1, its implementation was almost exactly as follows:

def NewType(name, type_):
    def identity(x):
        return x
    identity.__name__ = name
    return identity