FWIW I'm currently involved in implementing digitally signed packages
at work (no not mentioning where - most developers know anyway).
The product we ship (at least the software) is directly analgous to
NetBSD so I expect is the approach we are using.

As Thor has mentioned, what is required at the end of the day is for
the software installation process to be able to verify the
authenticity and integrity of the software to be loaded.

We're using a certificate based trust model - which is quite
appropriate to this case, since its the vendor's (eg NetBSD) code
wanting to confirm that the software to be loaded came from the
vendor. 

In OpenSSL a certificate is trusted if it can be located in a "trust
store" (default is something like /etc/certs or /etc/ssl/certs).
The basic purpose of a certificate is to bind a key to an identity,
and they can also limit the use of that key.  GPG has similar
functionality of course.

If a normal package is just a tar file (.tgz), you can wrap it into a
"signed" package containing.

package.tgz		the real package
package.tgz.sha1	SHA1 digest
package.tgz.sig		signed form of package.tgz.sha1
certs.pem		the certificate chain needed to verify
			that signature.

The certs.pem should contain at minimum the certificate for the key
used to generate the .sig

You can get fancy with the content of .sig but at minimum 
the .sig can be produced by just:

openssl sha1 -sign <keyfile> <thing> | openssl base64 > <thing>.sig

the base64 is optional but a good idea, in the above <keyfile> is a
PEM encoded private key, for which <cert> holds the public key and the
identity it is bound to etc.

Verification of the signature is a little messier (because sha1 is
lame about extracting a pubkey from a cert):

openssl base64 -d <thing>.sig > <thing>.sig.raw 
openssl x509 -noout -pubkey < <cert> > pubkey
openssl sha1 -verify pubkey -signature <thing>.sig.raw  < <thing>

The result would be one of:
Verified OK
Verification Failure
and an appropriate exit status.  


If the signature verifies, you now want to verify the cert:

openssl verify <cert>

All the above can of course be neatly bound in a script or a slick
binary - ie linked into your pkg_*

The astute reader will note the absense of any key generation above.
I left this to last, because its a huge subject which I don't have
time to cover fully.

The most trivial key generation is just:

openssl req -x509 -newkey rsa:2048 -keyout <keyfile> -out <cert>

eg.
openssl req -x509 -newkey rsa:512 -keyout privkey -out cert
Generating a 512 bit RSA private key
...............++++++++++++
.++++++++++++
writing new private key to 'privkey'
Enter PEM pass phrase:
Verifying - Enter PEM pass phrase:
-----
You are about to be asked to enter information that will be incorporated
into your certificate request.
What you are about to enter is what is called a Distinguished Name or a DN.
There are quite a few fields but you can leave some blank
For some fields there will be a default value,
If you enter '.', the field will be left blank.
-----
Country Name (2 letter code) [AU]:US
State or Province Name (full name) [Some-State]:CA
Locality Name (eg, city) []:
Organization Name (eg, company) [Internet Widgits Pty Ltd]:Crufty
Organizational Unit Name (eg, section) []:NET
Common Name (eg, YOUR name) []:sjg
Email Address []:sjg@crufty.net

which would produce a self-signed cert in <cert> which you can view
with

openssl x509 -noout -text < cert


Certificate:
    Data:
        Version: 3 (0x2)
        Serial Number: 0 (0x0)
        Signature Algorithm: md5WithRSAEncryption
        Issuer: C=US, ST=CA, O=Crufty, OU=NET, CN=sjg/emailAddress=sjg@crufty.net
        Validity
            Not Before: May 13 18:23:22 2004 GMT
            Not After : Jun 12 18:23:22 2004 GMT
        Subject: C=US, ST=CA, O=Crufty, OU=NET, CN=sjg/emailAddress=sjg@crufty.net
        Subject Public Key Info:
            Public Key Algorithm: rsaEncryption
            RSA Public Key: (512 bit)

Note that the Subject and Issuer names are the same.  
The only time you'd actually do this is when generating a top level CA
cert, in which case you'd do a lot more than the above - eg, you don't
want the cert to expire within say 30 years ;-)

Normally you'd generate what's called a Certificate Signing Request
(CSR) with:

openssl req -newkey rsa:2048 -keyout <keyfile> -out <csr>

same command as above but leaving out the -x509.
You'd then send <csr> to your CA of choice along with DNA samples or
whatever they require to agree to sign your cert, and they'll send you
back a <cert>.

That may sound like a lot of mucking about - especially compared to 
the peer to peer model of GPG or SSH, but it has advantages in terms of
scalability (which are perhaps not particularly important here).

If the trust store (eg /etc/certs/) contains CruftyCA.pem  actually it
needs 21b00b1d.0@ -> CruftyCA.pem since it is the hash of the Issuer
name that is used for lookups, then any certificate issued by
CruftyCA will verify successfully.

Full discussion of key management will have to wait another post...

Hope that helps.
--sjg