Q:

In make, how do I run prequisites exactly once? 

Let's pretend I have two servers A and B that I want to have the ability to deploy to separately and together in Makefile targets.  Let's also say there's a preparation step that I want to run exactly once before any deployment, whether it's to one or both.  How could I do that? 
Here's what I have so far, but it's not DRY. 
clean:
    # do cleanup stuff

deploy:
    make clean
    ssh $(SERVER) do-remote-deployment-stuff

deploy-to-a:
    deploy SERVER=myservera

deploy-to-b:
    deploy SERVER=myserverb

deploy-all:
    deploy-to-a
    deploy-to-b

See how it'd run 'clean' twice? 

A:

Instead of using recursion, just put the target you only want to run once as a prerequisite:
deploy-to-a: clean
        ...
deploy-to-b: clean
        ...

However, your attempt to set SERVER= etc.  won't work, and neither will your deploy-all rule.   You can't put make targets into make recipes.   You can use pattern rules:
SERVERS = A B

A_SERVER = myservera
B_SERVER = myserverb

deploy-all: $(SERVERS:%=deploy-to-%)

deploy-to-%: clean
        ssh $($*_SERVER) do-remote-deployment-stuff

clean:
        # do cleanup stuff

