  The order domains are a class of commutative rings introduced by H{\o}holdt,
van Lint, and Pellikaan to simplify the theory of error control codes using
ideas from algebraic geometry. The definition is largely motivated by the
structures utilized in the Berlekamp-Massey-Sakata (BMS) decoding algorithm,
with Feng-Rao majority voting for unknown syndromes, applied to one-point
geometric Goppa codes constructed from curves. However, order domains are much
more general, and O'Sullivan has shown that the BMS algorithm can be applied to
decode all codes constructed from order domains by a suitable generalization of
Goppa's procedure for curves. In this article we will first discuss the
connection between order domains and valuations on function fields over a
finite field. Under some mild conditions, we will see that a general projective
variety over a finite field has projective models which can be used to
construct order domains and Goppa-type codes for which the BMS algorithm is
applicable. We will then give a slightly different interpretation of Geil and
Pellikaan's extrinsic characterization of order domains via the theory of
Gr\"obner bases, and show that their results are related to the existence of
toric deformations of varieties. To illustrate the potential usefulness of
these observations, we present a series of new explicit examples of order
domains associated to varieties with many rational points over finite fields:
Hermitian hypersurfaces, Grassmannians, and flag varieties.
