How to make a method cancelable without it becoming ugly?

If the steps are somehow independend regarding the dataflow within the method, but can't be executed in a parallel matter, the following approach may be better readable:

void Run()
{
    // list of actions, defines the order of execution
    var actions = new List<Action<CancellationToken>>() {
       ct => Step1(ct),
       ct => Step2(ct),
       ct => Step3(ct) 
    };

    // execute actions and check for cancellation token
    foreach(var action in actions)
    {
        action(cancellationToken);

        if (cancellationToken.IsCancellationRequested)
            return false;
    }

    return true;
}

If the steps don't need the cancellation token because you can split them up in tiny units, you can even write a smaller list definition:

var actions = new List<Action>() {
    Step1, Step2, Step3
};

what about continuation?

var t = Task.Factory.StartNew(() => Step1(cancellationToken), cancellationToken)
   .ContinueWith(task => Step2(cancellationToken), cancellationToken, TaskContinuationOptions.OnlyOnRanToCompletion, TaskScheduler.Current)
   .ContinueWith(task => Step3(cancellationToken), cancellationToken, TaskContinuationOptions.OnlyOnRanToCompletion, TaskScheduler.Current);

I admit it isn't pretty, but the guidance is to either do what you have done:

if (cancellationToken.IsCancellationRequested) { /* Stop */ }

...or the slightly shorter:

cancellationToken.ThrowIfCancellationRequested()

Generally, if you can pass the cancellation token to the individual steps, you can spread the checks out such that they don't saturate the code. You may also choose not to check for cancellation constantly; if the operations you are performing are idempotent and aren't resource intensive, you don't necessarily have to check for cancellation at every stage. The most important time to check is before returning a result.

If you're passing the token to all of your steps, you could do something like this:

public static CancellationToken VerifyNotCancelled(this CancellationToken t) {
    t.ThrowIfCancellationRequested();
    return t;
}

...

Step1(token.VerifyNotCancelled());
Step2(token.VerifyNotCancelled());
Step3(token.VerifyNotCancelled());

When I had to do something like that, I created a delegate to do it:

bool Run(CancellationToken cancellationToken)
{
    var DoIt = new Func<Action<CancellationToken>,bool>((f) =>
    {
        f(cancellationToken);
        return cancellationToken.IsCancellationRequested;
    });

    if (!DoIt(Step1)) return false;
    if (!DoIt(Step2)) return false;
    if (!DoIt(Step3)) return false;

    return true;
}

Or, if there is never any code between the steps, you can write:

return DoIt(Step1) && DoIt(Step2) && DoIt(Step3);