The basic idea is: The client has to create a hash that satisfies a certain condition: Like the first n-digits must be 0, or maybe "the last bytes (when interpreted as a single 32 number) must be larger than x".

So the client does this:

    from itertools import count
    import hashlib

    for i in count():
        h = hashlib.md5("some-nonce:%d" % i).hexdigest()
        if h.startswith("000000"):
            print i
            break

The value "some-nonce" is provided by the server. It also provides the difficulty by saying: I need you to find i which generates a hash that starts with 6 zeros.

So the client calculates hashes for a while, and then submits the value 2652076 to the server. The server can the trivially check if the client did its work correctly:

    $ echo -en "some-nonce:2652076" | md5sum
    00000066adb2fb37a8460da553721c39 # ok, the first 6 digits are 0

The server can simply increase the difficulty by requiring the client to return more leading zeros. Or, if it should be more finegrained, a value below a certain threshold.