I have this same exact situation. I have a java lib which depends on Restlet and is used by my GAE server and my Android client.
For the lib, I mark the restlet dependency as optional, and specify "provided" scope, since it is provided by the containing app. I use the jse edition when building the lib, but I don't think it would matter which one you use; as the interface is the same.
<dependency>
<groupId>org.restlet.jse</groupId>
<artifactId>org.restlet</artifactId>
<version>${restlet.version}</version>
<optional>true</optional>
<scope>provided</scope>
</dependency>
For my Android client, I specify the android edition:
<dependency>
<groupId>org.restlet.android</groupId>
<artifactId>org.restlet</artifactId>
<version>${restlet.version}</version>
</dependency>
And for my GAE service, I specify the gae edition:
<dependency>
<groupId>org.restlet.gae</groupId>
<artifactId>org.restlet</artifactId>
<version>${restlet.version}</version>
</dependency>