Muitos não sabem mas é possível implantarmos os dados de frete para que o OC informe os valores de forma offline no checkout. Pessoalmente, acho a solução mais viável no momento - uma vez que evita transtornos ao cliente, devido a erros na informação do frete, e deixa a loja mais independente em relação às atualizações de módulos desenvolvidos por terceiros ou às atualizações no site dos Correios.
Assim como ocorre com todo o processo de construção da loja (cadastro de produtos, customização do tema, etc...) a implantação dos valores de frete também exige paciência e um pouco de trabalho, que aumentará de acordo com a diversidade de itens e pesos. Portanto, possuindo a tabela de preços, será interessante cadastrar os dados que a princípio você deverá usar e outros mais, a fim de poupar tempo - caso a sua loja aumente em variedades de produtos e pesos.
Tentarei descrever aqui um passo-a-passo para o cadastro de valores de Sedex, podendo ser feito da mesma maneira com o PAC.
Testado no OC v1.4.9.1
1 - Para quem não tiver, deverá antes de tudo conseguir junto aos Correios as tabelas de preços de Sedex e PAC correspondentes aos pesos e regiões de envio. É importante possuir as tabelas cujos valores estejam de acordo com o seu estado de origem. Por isso não use tabelas retiradas da internet e sim consiga as suas para evitar preços errados e acabar tendo que pagar a difereça ou cobrar a mais do cliente.
Este é um exemplo de parte da tabela do Sedex:

2 - No painel de administrador, você deverá criar "zonas" para capital e interior em "configurações/localização".
Para isso, você pode editar as cidades já existentes identificando-as como capital e criar novas, identificando-as como interior. Faça com todas as 27 (ficando um total de 54 zonas).
Ex.:
Nome: Rio de Janeiro - Capital
Código: RJ-C
País: Brasil
Status: Habilitado
---------------------
Nome: Rio de Janeiro - Interior
Código: RJ-I
País: Brasil
Status: Habilitado

3 - Crie as "Geo-Zonas" em "configurações/localização" de acordo com a tabela dos Correios para cada região de envio, atribuindo a cada uma os estados correspondentes.
Ex.:
Sedex Local:
Nome: Sedex Local
Descrição: Sedex Local
País: Brasil
Zona: Rio de Janeiro - Capital *Neste caso você irá colocar o seu estado de origem, ou seja de onde os produtos serão enviados.
---------------------
Sedex Capital:
Nome: Sedex Capital
Descrição: sedex MG, PR, SC
País: Brasil
Zona: Minas Gerais - Capital
Zona: Parana - Capital
Zona: Santa Catarina - Capital
3 - Em "extensões/envio" ative o módulo "Envio Baseado no Peso".
Na tela de edição do módulo, você deverá inserir as informações de peso e preço da tabela de acordo com as "Geo-zonas" que você criou anteriormente. As informações possuem o seguinte padrão: peso:custo, peso:custo... Exemplo: Supondo que o envio de 1kg custe $14,50, 2kg $18,70 e assim por diante, a configuração será 1:14.50,2:18.70,... Não esqueça de habilitar o status.

No mais você deverá observar as outras configurações, adequando-as às suas necessidades, inabilitando as zonas, geo-zonas e formas de envio "default" do OC. É importante não esquecer de atribuir o peso de cada produto para que o valor apareça no checkout do cliente, ou do contrário ele será informado que não há forma de envio disponível.
É isso.
Att.,