Um web Service em .NET com um método de inserir um usuário através de uma Procedure (Nada mais é do que um insert simples com as variáveis).
Gostaria de saber o passos que eu tenho que fazer no Java para mandar os parâmetros e assim fazer a inserção.
Utilize Jax-ws. API Nativa do Java. Usando a anotation em uma classe de projeto EJB ou Dynamic Web Project, sendo ela @WebService e @WebMethod para os métodos que serão utilizados no seu serviço. Restante disso não muda nada a maneira de interagir com banco de dados.
Dê uma olhada neste link, um bom ponto de partida.
Sua pergunta é muito genérica amigo.
Dentro do java nos temos vários produtos para web services e vc tem a liberdade de escolher qualquer um deles.
O mais usado é o JAX-WS: