How to use a Servlet Filter to change/rewrite an incoming URL?

How can I use a Servlet Filter to change an incoming URL from

http://nm-java.appspot.com/Check_License/Dir_My_App/Dir_ABC/My_Obj_123

to

http://nm-java.appspot.com/Check_License?Contact_Id=My_Obj_123

?

Update: according to BalusC's steps below, I came up with the following code:

public class UrlRewriteFilter implements Filter {

    @Override
    public void init(FilterConfig config) throws ServletException {
        //
    }

    @Override
    public void doFilter(ServletRequest req, ServletResponse res, FilterChain chain) throws ServletException, IOException {
        HttpServletRequest request = (HttpServletRequest) req;
        String requestURI = request.getRequestURI();

        if (requestURI.startsWith("/Check_License/Dir_My_App/")) {
            String toReplace = requestURI.substring(requestURI.indexOf("/Dir_My_App"), requestURI.lastIndexOf("/") + 1);
            String newURI = requestURI.replace(toReplace, "?Contact_Id=");
            req.getRequestDispatcher(newURI).forward(req, res);
        } else {
            chain.doFilter(req, res);
        }
    }

    @Override
    public void destroy() {
        //
    }
}

The relevant entry in web.xml look like this:

<filter>
    <filter-name>urlRewriteFilter</filter-name>
    <filter-class>com.example.UrlRewriteFilter</filter-class>
</filter>
<filter-mapping>
    <filter-name>urlRewriteFilter</filter-name>
    <url-pattern>/*</url-pattern>
</filter-mapping>

I tried both server-side and client-side redirect with the expected results. It worked, thanks BalusC!