Depth-first Search Non-Reursive Implementation in Clojure
From the top ... 


The label function is a synonym for cons, as is build-stack for
concat. Drop them.
The get-edges function doesn't get edges. It gets the neighbouring
vertices. Call it neighbours, or some such.


The labeled? function:


It determines whether the first argument is a member of the
collection second argument. So call it something generic like
includes?.
Swap the arguments around, so that it reads more naturally.
Get rid of the explicit falses and trues. You usually can. 


We end up with

(defn includes?
  [coll x]
  (some #(= x %) coll))


Now for the dfs function itself. 


Your local S is, as its name suggests, a stack. Use the other end
of it - the front of the list. This gets rid of the slow last and
butlast. You can't use Clojure's stack lingo - peek, pop, and
conj - because there's a concat in there. So use first, next,
and cons instead.
If you use a vector instead of a list to accumulate discovered, you
don't need the final reverse.
(cons v ()) is just (list v)


The result is

(defn dfs
  [g v]
  (loop [discovered [], S (list v)]
    (cond
      (empty? S) discovered
      (includes? discovered (first S)) (recur discovered (rest S))
      :else (recur
              (conj discovered (first S))
              (concat (neighbours g (first S)) (rest S))))))




There's still a performance problem. Whenever it deals with a potentially new vertex, it uses includes? to do a linear search of discovered. For a graph of n vertices, this takes of the order of n^2 time. 

The answer is to hold the discovered data twice:


as a vector, for returning the answer; and
as a set, for testing for presence.


This roughly doubles the amount of memory required, but reduces time required enormously (roughly to order of n). 

I'll leave you to make the necessary changes to dfs.