We establish new characterizations of amenability of graphs through two probabilistic notions: stochastic domination and finitary codings (also called finitary factors). On the stochastic domination side, we show that the plus state of the Ising model at very low temperature stochastically dominates a high density Bernoulli percolation if and only if the underlying graph is nonamenable. This answers a question of Liggett and Steif. We prove a similar result for the ``infinite cluster process'' of Bernoulli percolation, which is of particular interest as this process is not monotone and does not possess any nice form of the domain Markov property. We also prove that the plus states of the Ising model at very low temperatures are stochastically ordered if and only if the graph is nonamenable. This answers a second question of Liggett and Steif. We further show that these stochastic domination results can be witnessed by invariant monotone couplings. On the finitary coding side, we show that the plus state of the Ising model at very low temperature is a finitary factor of an i.i.d. process if and only if the underlying graph is nonamenable (assuming it supports a phase transition). We show a similar result for the infinite cluster process of a high-density Bernoulli percolation. A main technique is to consider diluted processes, for which Holley's condition can be established. In order to compare two Ising models, we apply a dilution mechanism using lattice gas theory. Along the way we develop general tools to establish invariant domination when Holley's condition is satisfied. The finitary factor results are based on the stochastic domination results and a dynamical construction involving bounding chains, along with a new technique to analyze coupling from the past in infinite-range processes via a novel disease spreading model, which may be of independent interest.