Using num_holes=None as the default is fine if you are going to have just __init__.

If you want multiple, independent "constructors", you can provide these as class methods. These are usually called factory methods. In this case you could have the default for num_holes be 0.

class Cheese(object):
    def __init__(self, num_holes=0):
        "defaults to a solid cheese"
        self.number_of_holes = num_holes

    @classmethod
    def random(cls):
        return cls(randint(0, 100))

    @classmethod
    def slightly_holey(cls):
        return cls(randint(0, 33))

    @classmethod
    def very_holey(cls):
        return cls(randint(66, 100))

Now create object like this:

gouda = Cheese()
emmentaler = Cheese.random()
leerdammer = Cheese.slightly_holey()

One should definitely prefer the solutions already posted, but since no one mentioned this solution yet, I think it is worth mentioning for completeness.

The @classmethod approach can be modified to provide an alternative constructor which does not invoke the default constructor (__init__). Instead, an instance is created using __new__.

This could be used if the type of initialization cannot be selected based on the type of the constructor argument, and the constructors do not share code.

Example:

class MyClass(set):

    def __init__(self, filename):
        self._value = load_from_file(filename)

    @classmethod
    def from_somewhere(cls, somename):
        obj = cls.__new__(cls)  # Does not call __init__
        super(MyClass, obj).__init__()  # Don't forget to call any polymorphic base class initializers
        obj._value = load_from_somewhere(somename)
        return obj

All of these answers are excellent if you want to use optional parameters, but another Pythonic possibility is to use a classmethod to generate a factory-style pseudo-constructor:

def __init__(self, num_holes):

  # do stuff with the number

@classmethod
def fromRandom(cls):

  return cls( # some-random-number )

Why do you think your solution is "clunky"? Personally I would prefer one constructor with default values over multiple overloaded constructors in situations like yours (Python does not support method overloading anyway):

def __init__(self, num_holes=None):
    if num_holes is None:
        # Construct a gouda
    else:
        # custom cheese
    # common initialization

For really complex cases with lots of different constructors, it might be cleaner to use different factory functions instead:

@classmethod
def create_gouda(cls):
    c = Cheese()
    # ...
    return c

@classmethod
def create_cheddar(cls):
    # ...

In your cheese example you might want to use a Gouda subclass of Cheese though...

Those are good ideas for your implementation, but if you are presenting a cheese making interface to a user. They don't care how many holes the cheese has or what internals go into making cheese. The user of your code just wants "gouda" or "parmesean" right?

So why not do this:

# cheese_user.py
from cheeses import make_gouda, make_parmesean

gouda = make_gouda()
paremesean = make_parmesean()

And then you can use any of the methods above to actually implement the functions:

# cheeses.py
class Cheese(object):
    def __init__(self, *args, **kwargs):
        #args -- tuple of anonymous arguments
        #kwargs -- dictionary of named arguments
        self.num_holes = kwargs.get('num_holes',random_holes())

def make_gouda():
    return Cheese()

def make_paremesean():
    return Cheese(num_holes=15)

This is a good encapsulation technique, and I think it is more Pythonic. To me this way of doing things fits more in line more with duck typing. You are simply asking for a gouda object and you don't really care what class it is.

Use num_holes=None as a default, instead. Then check for whether num_holes is None, and if so, randomize. That's what I generally see, anyway.

More radically different construction methods may warrant a classmethod that returns an instance of cls.

Overview

For the specific cheese example, I agree with many of the other answers about using default values to signal random initialization or to use a static factory method. However, there may also be related scenarios that you had in mind where there is value in having alternative, concise ways of calling the constructor without hurting the quality of parameter names or type information.

Since Python 3.8 and functools.singledispatchmethod can help accomplish this in many cases (and the more flexible multimethod can apply in even more scenarios). (This related post describes how one could accomplish the same in Python 3.4 without a library.) I haven't seen examples in the documentation for either of these that specifically shows overloading __init__ as you ask about, but it appears that the same principles for overloading any member method apply (as shown below).

"Single dispatch" (available in the standard library) requires that there be at least one positional parameter and that the type of the first argument be sufficient to distinguish among the possible overloaded options. For the specific Cheese example, this doesn't hold since you wanted random holes when no parameters were given, but multidispatch does support the very same syntax and can be used as long as each method version can be distinguish based on the number and type of all arguments together.