What does he mean by interface and implementation and what does simplicity mean for each of them?

Don’t think too much about it, it’s just English.

He means your code’s interface (not necessarily interfaces!) – how people work with your code. And your code’s implementation – how your code actually does the things it needs to do. And simple is simple – is your stuff easy to work with.

Simplicity in interface means it’s easy to use your stuff. Do your functions have good names with obvious parameters and few side effects? Do they do what your users need? Do your classes have good names with obvious functionality? Do they do what your users need? Without too much trouble?

Simplicity in implementation means it’s easy for programmers (or you) to work with your stuff. Can you modify the code easily? Can you test it easily? Can you understand it? Debug it?

While simple implementation often yields simple interface, it’s not always the case. Some of the best designs isolate bits of necessarily complex implementation behind a simple interface. Likewise, if the easiest implementation isn’t what your users need, you can end up with a complex interface.

The page seems to be using those terms literally, without reference to any particular programming construct, so there isn’t really anything to define. Instead I’ll try giving an example.

Say you have a class that gets things from the internet. Here’s a simple interface version:

class Internet {
    int sendRequest(const std::string& url, std::string& response);
}

Internet::sendRequest(const std::string& url, std::string& response) {
    // parse the url into its various tokens
    m_protocol = /* first token, or https if not provided */
    m_domain = /* second token */
    while(...) { m_parameters.push_back(/* another token */); }
    ...
    switch(m_protocol) {
        case HTTPS: HTTPSImpl.request(m_domain, ...); break;
        ...
    }
}

Here’s a simple implementation version:

class Internet {
    int setProtocol(Internet::Protocol protocol);
    int setDomain(const std::string& domain);
    int addParameter(...);
    ...
    int sendRequest(std::string& response);
}

Internet::request(std::string& response) {
    switch(protocol) {
        case HTTPS: HTTPSImpl.request(m_domain, ...); break;
        ...
    }
}

Essentially it’s a trade-off between making the implementer deal with the complexity versus the interface user. Most of the time you’ll be (rightfully) told that hiding complexity from the user is a good thing, but Richard Gabriel’s page argues that that might not always be the case.