How would I overload method in an interface?

An interface serves as a contract for the users of that interface: you specify what methods are available (in all implementations) and how they are called. If two implementations of an interface need a different method, then that method should not be part of the interface:

public interface Lookup {
}

public class MapLookup implements Lookup {
    public String getValue(String key) {
        //...
    }
}

public class GuavaLookup implements Lookup {
    public String getValue(String row, String column) {
        // ...
    }
}

In your program, you will know which implementation you use, so you can simply call the right function:

public class Program {
    private Lookup lookup = new MapLookup();

    public void printLookup(String key) {
        // I hardcoded lookup to be of type MapLookup, so I can cast:
        System.out.println(((MapLookup)lookup).getValue(key));
    }
}

Alternative approach

If your class Program is more generic and uses dependency injections, you may not know which implementation you have. Then, I would make a new interface Key, which can be either type of key:

public interface Lookup {
    // ...

    public String getValue(Key key);
}

public interface Key {
}

public MapKey implements Key {
    private String key;
    // ...
}

public GuavaKey implements Key {
    private String row, column;
    // ...
}

The dependency injection in your program might come from some factory implementation. Since you cannot know which type of lookup you use, you need a single contract for getValue.

public interface Factory {
    public Lookup getLookup();
    public Key getKey();
}

public class Program {
    private Lookup lookup;

    public Program(Factory factory) {
        lookup = factory.getLookup();
    }

    public void printLookup(Factory factory) {      
        System.out.println((lookup.getValue(factory.getKey()));
    }
}

As of Java 8, you can have an interface provide an implementation of a method, through the use of the default keyword. Therefore a new solution would be to provide a default implementation of both methods which maybe throws an exception, then derive the actual implementation from the default interface.

Anyways here is how you can do this:

public interface SomeInterface {
    // method 1
    default String getValue(String arg1) {
        // you decide what happens with this default implementation
    }

    // method 2
    default String getValue(String arg1, String arg2) {
        // you decide what happens with this default implementation
    }
}

Finally, make the classes override the correct methods

public class SomeClass1 implements SomeInterface {
    @Override
    public String getValue(String arg1) {
        return arg1;
    }
}

public class SomeClass2 implements SomeInterface {
    @Override
    public String getValue(String arg1, String arg2) {
        return arg1 + " " + arg2;
    }
}

A solution (not very elegant) might look loke this:

public abstract class SomeClass {
   public String getValue(String arg1) {
      throw new IllegalArgumentException();
   }
   public String getValue(String arg1, String arg2) {
      throw new IllegalArgumentException();
   }
}

public class SomeClass1 extends SomeClass {
   public String getValue(String arg1) {
      // return sth
   }
}

public class SomeClass2 extends SomeClass {
   public String getValue(String arg1, String arg2) {
      // return sth
   }
}

However there's a drawback - SomeClass1 and SomeClass2 can't inherit directly other class.