I'm trying to use type hinting to differentiate between two single-arg methods.

For example, add-vertex is wrapping a Java method that can take a variable number of args, and so here I am trying to make add-vertex take zero, one, or two args...

(defmulti add-vertex (fn [& args] (map class args)))
(defmethod add-vertex [] (add-vertex nil nil))
(defmethod add-vertex Integer [id] (add-vertex id nil))
(defmethod add-vertex Map [props] (add-vertex nil props))
(defmethod add-vertex [Integer Map] [id props]
  ((let [vertex (. *g* addVertex id)]
    (when props
      (apply set-props vertex (interleave (map name (keys props)) (vals props))))
    vertex)))

Notice there are two singe-arg funcs -- each taking a different type (id is a Java Integer and props is a Java Map). I'm new to Clojure so I suspect I'm doing this totally wrong.

Here is the code for what you are trying to do:

(defmulti add-vertex (fn [& args] (map class args)))
(defmethod add-vertex [] [] (add-vertex nil nil))

;; You could also use java.lang.Integer here, but numbers are Longs by default
(defmethod add-vertex [java.lang.Long] [id]
                                       (add-vertex id nil))

;; I assume you are using a clojure map ie {:1 2}
(defmethod add-vertex [clojure.lang.PersistentArrayMap] [props]
                                                        (add-vertex nil props))

(defmethod add-vertex [java.lang.Long clojure.lang.PersistentArrayMap] [id props] ...)

But as you can see this gets pretty messy with the classes.

An alternate solution might be to do something like this:

(defn dispatch-fn
  ([] :empty)
  ([a] (cond
         (number? a) :number
         (map? a)    :map
         :else       :error))
  ([a b] (if (and (number? a) (map? b))
             :number-and-map
             :error))
  ([a b & args] :error))

(defmulti add-vertex dispatch-fn)
(defmethod add-vertex :empty [] (add-vertex nil nil))
(defmethod add-vertex :number [id] (add-vertex id nil))
(defmethod add-vertex :map [props] (add-vertex nil props))
(defmethod add-vertex :number-and-map [id props] ...)
(defmethod add-vertex :error [& args] ...)