動的でない場合

これはよく紹介されている方法で、基本文法だと思います。

'{0:05d}'.format(12)  #=> '00012'

ゼロ埋めとは関係ないですが、スペースで埋めるには以下のような感じですね。

'{0:5d}'.format(12)  #=> '   12'

動的にする場合

Pythonでは {0:05d} のようなフィールドに変数が使えないのでこの記法では「動的に桁数を指定して文字列を得る」ということができません。

なので、以下の方法で実現することができます。

# -*- coding: utf-8 -*-

max = 10000  #<= これが動的になる想定

# 最大桁を得る
max_len = len(str(max))
# 対象の数値（今回は適当）
test = 123

### 対象の数値に対して最大桁でゼロ埋め ###
# `zfill`を使う場合
output = str(test).zfill(max_len)
print(output)  #=> '00123'

# rjustを使う場合
output = str(test).rjust(max_len,'0')
print(output)  #=> '00123'

zfill を使うことで引数で指定する桁数に変数が使えるようになるのを利用しています。

また、rjustを使えば、0以外の文字を第二引数に指定すればゼロ以外の文字で埋めることができます。
（rjustを使う方法は @matobaa san より教えていただきました。 thanx @matobaa san!）